Brackets parade
Find the number of different correct bracket sequences consisting of k[1] pairs of brackets of the first type, k[2] pairs of brackets of the second type, ..., k[m] 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 k[1], k[2], ..., k[m] follow each separated with a space. k[i] 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.