Count the number of different correct bracket sequences consisting of k1 pairs of brackets of the 1st type, k2 pairs of brackets of the 2nd type … km pairs of brackets of the 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 (_iA)_i is correct where (_i and )_i are opening and closing brackets of the same type.

Input

The first line of input is the number 0 < n ≤ 1000 of test cases. Each of the following n lines describe a test case. Each line starts with number 0 < m ≤ 100 the amount of different bracket types. Then m positive numbers k1, k2 … km follow each separated with a space. Number ki is the amount of pairs of brackets of 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.

Example

Input:
3
1 4
2 2 2
3 1 2 3

Output:
14
84
7920