COLORF - Colorful Blocks
Rith, the student of the month has received k sets of colored blocks. Each set is of a different color and each block in a set is identical to any other block. Rith has n-types of colors and has a1, a2, a3 ... an number of blocks for each color respectively. He arranges these blocks in a straight line, and wants to know the number of ways he can arrange it. Please help him find out the number of ways. Oh and Rith knows that this number will be very large, and hence asks you to find it modulo 1,000,000,009 (A number modulo P is the remainder that is left after dividing that number by P)
For example if Rith has 2 types of colors and {a1,a2} = {1,2}
Then the following arrangemenets are possible
(Digit here means the color)
122
212
221
Hence the answer is 3.
Input
The first line contains an integer T, which is the number of test cases. Then there are T-test case blocks which follow.
Each test-case block starts with an integer n, which is the number of types of colors.
The next line contains n-integers a1, a2, a3 ... an as described in the statement.
T <= 100
1 <= n <= 100
a1 + a2 + a3 .. + an <= 200,000
Output
Print the number of ways as described modulo 1,000,000,009
Example
Input:
3
2
1 2
3
1 1 1
5
200 200 200 200 200
Output:
3
6
706392408
Added by: | .:: Pratik ::. |
Date: | 2011-03-07 |
Time limit: | 1.508s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |