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