/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
3N 本の棒があります。i 番目の棒の長さは A_i です。
この棒を 3 本 1 組に分け、N 個の三角形を作る方法は何通りありますか？
ただし、N 個の三角形を作る 2 つの方法は、一方では三角形をなしているある 3 本の組が、他方では三角形をなしていないとき、かつそのときに限り異なるとみなします。
詳細は入力例 1 の説明を参照してください。
制約
- 1 \leq N \leq 4
- 1 \leq A_i \leq 100
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 \ldots A_{3N}
出力
答えを出力せよ。
入力例 1
2 3 3 3 4 4 6
出力例 1
7
i,j,k 番目の 3 本の棒を使って作ることができる三角形を (i,j,k) と表すことにします。
以下の 7 通りの方法があります。同じ長さの棒も区別することに注意してください。
- (1,2,3),(4,5,6)
- (1,2,4),(3,5,6)
- (1,2,5),(3,4,6)
- (1,3,4),(2,5,6)
- (1,3,5),(2,4,6)
- (2,3,4),(1,5,6)
- (2,3,5),(1,4,6)
なお、例えば、1,2,6 番目の棒を組み合わせることでは三角形を作ることができません。
入力例 2
4 100 100 100 100 100 100 100 100 100 100 100 100
出力例 2
15400
Problem Statement
There are 3N sticks. The length of the i-th stick is A_i.
How many ways are there to group them into triplets so that they form N triangles?
Here, two ways to form N triangles are distinguished if and only if there is a triplet forming a triangle in one way that does not form a triangle in the other way.
For more details, see the description of Sample Input 1.
Constraints
- 1 \leq N \leq 4
- 1 \leq A_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 \ldots A_{3N}
Output
Print the answer.
Sample Input 1
2 3 3 3 4 4 6
Sample Output 1
7
We denote by (i,j,k) the triangle formed by the following three sticks: i-th, j-th, and k-th.
There are seven ways as follows. Note that equal-length sticks are distinguished.
- (1,2,3),(4,5,6)
- (1,2,4),(3,5,6)
- (1,2,5),(3,4,6)
- (1,3,4),(2,5,6)
- (1,3,5),(2,4,6)
- (2,3,4),(1,5,6)
- (2,3,5),(1,4,6)
On the other hand, for instance, the 1-st, 2-nd, and 6-th sticks do not form a triangle.
Sample Input 2
4 100 100 100 100 100 100 100 100 100 100 100 100
Sample Output 2
15400