The description provided for this problem:
Agent Ω has discovered that The Serpent has been funneling funds to C.H.I.M.E.R.A. to build a space warship, hidden above the Martian north pole. The biggest challenge with stopping the ship is that it has A.I. torpedoes swarming around it, controlled by smart bricks. But if Agent Ω can figure out which bricks they are, she'll be able to deactivate them remotely, making them drift off course.
After stealing the plans for the torpedos, Agent Ω figures out exactly how long the compartment is that stores the smart chain contoller. She knows EXACTLY how long the chain is, but not what bricks make it up. Given that different types of bricks have different lengths, can you determine how many possible series of bricks exist that are a given total length when chained together?
Given N types of bricks where brick type i has length Li , how many ways are there to lay them in a line with total length of exactly Ltotal ? Note that order DOES matter.
Input Format
The first line of the input provides T, the total number of test cases.
The next T pairs of lines describe a single test case:
The first line in a test case privides the number of brick types (N) and the total target length ( Ltotal ).
The second line has N values, each position i indicating the length of brick brick type i.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 50
1 ≤ Ltotal ≤ 106
1 ≤ Li ≤ 106
Output Format
T lines, one per test case, each indicating the number of combinations possible to make a line of that total length. Some of the values are quite large, so mod your answer by 1000000009.
Example 0
Sample Input
2
2 5
1 2
2 7
1 3
Sample Output
8
9
Explanation
There are 2 test cases. In the first we have 2 brick types, one of length 1 and the other of lenth 2. We must make a chain of length five using these two types. Let's call the first brick A and the second BB (since it's length two). We can then figure out all of the possible brick layouts of length 5:
A A A A A
A A A BB
A A BB A
A BB A A
BB A A A
A BB BB
BB A BB
BB BB A
For a total of 8 different options.
For the second test case, there are again 2 types of bricks. The first one is length 1 and the second is length 3. We need them to have a total length of 7. If we call the bricks A and CCC, the options this time are:
A A A A A A A
A A A A CCC
A A A CCC A
A A CCC A A
A CCC A A A
CCC A A A A
A CCC CCC
CCC A CCC
CCC CCC A
For a total of 9 different options.
