Find the number of different correct bracket sequences consisting of k1 pairs of brackets of the first type, k2 pairs of brackets of the second 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 (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 k1, k2, ..., km follow each separated with a space. ki is the number 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.