Brackets parade#230

Brackets parade

1 second

128 megabytes

Very easy

Find the number of different correct bracket sequences consisting of $k_{1}$ k_1 pairs of brackets of the first type, $k_{2}$ k_2 pairs of brackets of the second type, ..., $k_{m}$ k_m pairs of brackets of the $m$ -th type.

A bracket sequence is considered correct if:

The empty sequence is correct;
If $A$ is correct and $B$ is correct, then $A B$ is correct;
If $A$ is correct, then $(A)$ is correct, where $($ and $)$ are the opening and closing brackets of the same type.

Input

The first line contains the number of test cases $n$ ( $0 < n \leq 1000$ 0 < n \leq 1000). Each of the following $n$ lines describes a test case. Each line starts with the number $m$ ( $0 < m \leq 100$ 0 < m \leq 100), the number of different types of brackets. Then $m$ positive integers $k_{1}, k_{2}, \dots, k_{m}$ k_1, k_2, \ldots, k_m follow, each separated by a space. Here, $k_{i}$ k_i is the number of pairs of brackets of the $i$ -th type. The total number of bracket pairs does not exceed $1000$ .

Output

For each test case, output a line containing a single integer: the answer to the problem modulo $1000000007$ .

Examples

Example 1

Loading

k_{1}

k_{2}

k_{m}

0 < n \leq 1000

0 < m \leq 100

k_{1}, k_{2}, \dots, k_{m}

k_{i}