hackercupai/hackercup huggingface dataset:
There are **K** families living in Christmasville. During Christmas they have
this tradition, where each person secretly gets a gift for some other person.
The assignment of who gives gift to whom is generally done by a lottery, but
this time we are writing a program to do it.

The assignment should have the following properties:
* Each person should give exactly one gift.
* Each person should receive exactly one gift.
* A person should not give a gift to someone within the same family.

Find out how many possible assignments are there, that satisfy above
constraints. Two assignments are considered different, if there exists some
person, who gives gifts to different people in the two assignments. Since this
number may be very large, output this number modulo **1,000,000,007**

### Input

The first line of the input consists of a single integer **T**, the number of
test cases.
Each test case starts with a line containing the integer **K**, the number of
families.
The next line of each test case contains **K** integers, **n1**, **n2**, ...,
**nK**, where **ni** is the number of people in the **i**th family.

### Output

For each test case **i** numbered from 1 to **T**, output "Case #**i**: ",
followed by the number of valid assignments, modulo 1,000,000,007

### Constraints

1 ≤ ** T ** ≤ 20
2 ≤ ** K ** ≤ 100
1 ≤ **ni** ≤ 4
1 ≤ **n1** \+ **n2** \+ ... + **nK** ≤ 100