# Азербайджан - подготовка. Март 18

# Brackets parade

Find the number of different correct bracket sequences consisting of `k`

pairs of brackets of the first type, _{1}`k`

pairs of brackets of the second type, ..., _{2}`k`

pairs of brackets of the _{m}**m**-th type. The bracket sequence is considered correct in the following cases:

- empty sequence is correct;
- if
**A**is correct and**B**is correct then**AB**is correct; - if
**A**is correct then**(A)**is correct where**(**and**)**are opening and closing brackets of the same type.

#### Input

The first line is the number **n** (**0** < **n** ≤ **1000**) of test cases. Each of the following **n** lines describe a test case. Each line starts with number **m** (**0** < **m** ≤ **100**) the amount of different bracket types. Then **m** positive numbers `k`

, _{1}`k`

, ..., _{2}`k`

follow each separated with a space. _{m}`k`

is the number of pairs of brackets of _{i}**i**-th type. The total amount of pairs of brackets is not greater than **1000**.

#### Output

For each test case output a line containing single integer – the answer to the problem modulo **1000000007**.

3 1 4 2 2 2 3 1 2 3

14 84 7920