BRPAR  Brackets Parade
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 mth 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 (_{i}A)_{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 ith 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
hide comments
Piyush Kumar:
20160621 13:06:55
People complaining about the TL, it is not at all strict. You must find the right solution. 

xpshekhar:
20151224 21:13:34
can anyone explain how the cases are working?


moustafa maher:
20130911 10:06:41
Can you extend the time to 20 second ,,, to pass my code and return it back to 1 after that


abualy:
20111103 22:14:15
how can it be done in java?? :s


Spooky:
20110824 15:36:34
nope... this can be derived from the definition... 

Ivan Sto¹iæ:
20110819 23:58:51
is <open1><open2><closed1><closed2> a correct sequence? 

Naveen Jaiswal:
20110518 18:52:29
how will one bracket even exist? 

numerix:
20100205 18:15:11
No. 

Bommisetty Indraneel:
20100103 00:05:58
I guess time limit is too tight for python? 
Added by:  Spooky 
Date:  20090411 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Open AllUkrainian Collegiate Contest SemiFinal, 2009 