COLORF - Colorful Blocks

no tags 

 

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.

 

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