Sr. Lee and Jr. Lee are brothers worked in a pizza house. Everyday Jr. Lee has to deliver pizza to exactly one nearby family. The pizza house is located at position 0 on a long straight road. On that road, at position a1, a2, ..., an there are families that would likely order a pizza for lunch. On the end of June Sr. Lee asked Jr. Lee to report the total distance that he had gone through. Please help Sr. Lee to calculate how many ways that Jr. Lee can deliver pizza these days. For example, if a1=2, a2=3 and total distance D=16, then there are exactly 4 ways that Jr. Lee could have delivered pizza: (a1,a1,a1,a1), (a1,a2,a2), (a2,a1,a2), (a2,a2,a1). Note that we did NOT care about number of delivering days.
Oh, by the way, Sr. Lee and Jr. Lee are trying to sell new kind of food -- dumplings, but soon Jr. Lee quit his job.
The first line of the input file contains an integer T (1<= T<= 100) indicating the number of test cases.
For each test case, first line contains two integers n, D (1<= n<= 100; 1<= D<= 200000). Second line contains n positive integers a1, a2, ..., an. (1<= ai<= 1000).
For each test case, please output the number of ways modulo 1000000007.
3 1 9 10 1 20 10 2 16 2 3
0 1 4
Migrated from old NTUJ.
Tmt, Ferng
| No. | Testdata Range | Score |
|---|