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 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

Added by:Spooky
Date:2009-04-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Open All-Ukrainian Collegiate Contest Semi-Final, 2009

hide comments
2016-06-21 13:06:55 Piyush Kumar
People complaining about the TL, it is not at all strict. You must find the right solution.
2015-12-24 21:13:34
can anyone explain how the cases are working?
2013-09-11 10:06:41 moustafa maher
Can you extend the time to 20 second ,,, to pass my code and return it back to 1 after that
!!!!!
2011-11-03 22:14:15 abualy
how can it be done in java?? :s

re: don't use BigInteger

Last edit: 2011-11-04 12:42:45
2011-08-24 15:36:34 Spooky
nope... this can be derived from the definition...
2011-08-19 23:58:51 Ivan Sto¹iæ
is <open1><open2><closed1><closed2> a correct sequence?
2011-05-18 18:52:29 Naveen Jaiswal
how will one bracket even exist?
2010-02-05 18:15:11 numerix
No.
2010-01-03 00:05:58 Bommisetty Indraneel
I guess time limit is too tight for python?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.