Under construction

Still being built. Things may change

Radar Chart

Time limit2sMemory limit1024 MB

Summary
Count the orderings of 8 stats around the octagon so that the radar chart is a convex polygon.
Level

Medium4 of 10

Topics
Brute force, Geometry, Implementation
Solved
No attempts yet

Problem

A radar chart is a common way to show a game character's stats at a glance. A character has 8 stats. If the stats are a_1,a_2,⋯ ,a_8a\_1, a\_2, \cdots, a\_8, the graph is an octagon, and the kk-th vertex is a_ka\_k away from the origin in the direction of 45×k45\times k degrees.

A radar chart shows how evenly the stats are distributed. If all stats are equal, the shape is a regular polygon. If one stat is much lower than the others, the polygon is concave. Many people try to make the graph a convex polygon, meaning every interior angle is at most 180°180°, so that they can remove their weak spots.

Siru wants to turn his graph into a convex polygon, but raising stats is tedious. So he came up with a trick: change the order in which the stats are listed. For example, the list {6,7,7,8,9,10,11,13}\{6,7,7,8,9,10,11,13\} gives a concave polygon, but the list {7,6,7,8,9,10,11,13}\{7,6,7,8,9,10,11,13\} gives a convex polygon.

The order of the stats decides whether the polygon is concave or convex. Find the number of ways to arrange the stats so that the radar chart is a convex polygon.

Input

The first line contains 8 integers a_1,a_2,⋯ ,a_8a\_1, a\_2, \cdots, a\_8, the stats, separated by spaces. (1≤a_i≤1041 \leq a\_i \leq 10^4)

Output

Print the number of ways to arrange the 8 stats so that the radar chart is a convex polygon.

Examples2

  1. Example 1

    Input
    1 1 1 1 1 1 1 1
    
    Expected output
    40320
    
  2. Example 2

    Input
    6 7 7 8 9 10 11 13
    
    Expected output
    7712