Regular Octahedron

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Ronhou is so lovely that he must be a boy~He has collected some sticks of equal length which have at most m kinds of colors,

and the number of sticks of the ith color is a[i](i=1,2,...,m).

(Note:There is only one kind of color to a stick).

Please use twelve of them to make up a regular octahedron,and tell Ronhou how many different regular octahedrons can be made up.

Two regular octahedrons are considered equal if one of them could be rotated with a line in 3-d space and put next to the other 

such that the corresponding edges of the two regular octahedrons are equally colored.

Input

The first line of input contains an integer T (T ≤ 100),indicating the number of cases.Then T lines follow.Each case two lines.

The first line consists of an integer m (1 ≤ m ≤ 6),and the second line consists of m integers a[1],a[2],...,a[m] (a[i] ≥ 0).

no color will be the same.The number of sticks of all kinds of colors will not exceed 100.

Output

Each case a line,and output the case number first,then a single integer,indicating the number of different regular octahedron.

The answer should be moduloed by 1000000007.

Sample Input

4
4
0 11 0 1
6
0 0 10 0 2 0
6
0 0 11 0 2 0
5
1 2 3 3 3

Sample Output

Case #1: 1
Case #2: 5
Case #3: 6
Case #4: 46200

Source

Shoutmon

Manager

Information
Solved Number6
Submit Number9
Problem Tags
combinatorics
dfs and similar
number theory
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel