406360: GYM102388 F Shopping

On Planet E, people like shopping a lot!

However they do not have electronic payments and can only pay by coins. There are $$$n$$$ different coins on Planet E, with different integral values $$$c_0, c_1, \dots, c_{n - 1}$$$ respectively. The cashiers on Planet E always have infinite number of each coins for changes, and hence very often there are multiple ways to give an $$$m$$$ dollar change.

The people on Planet E believe that the number of ways to give change affect their luck throughout the day, but it is too hard for them to count the number.

Can you help the people on Planet E to count the number of ways to give change? Since the number may be huge, you only need to answer the number module $$$1000000007$$$ ($$$10^9 + 7$$$).

The first line contains a positive integer $$$T$$$ ($$$T \le 10$$$), the number of testcases.

Each testcase starts with a line consisting of two integers $$$n, m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 10000$$$), the number of coins and the amount of change. Then the following line consists of $$$n$$$ integers $$$c_0, c_1, \dots, c_{n - 1}$$$ ($$$1 \le c_i \le 10000$$$), the coin values.

For each testcase, output a single line consisting of the number of ways to give exactly $$$m$$$ dollar change, module $$$10^9 + 7$$$.

5
1 100
1
4 10
5 7 2 3
3 100
1 2 3
4 100
101 102 103 104
5 10000
5 4 3 2 1

1
5
884
0
649632988

In the second case, the five ways are 3 + 7, 5 + 5, 2 + 3 + 5, 2 + 2 + 3 + 3 and 2 + 2 + 2 + 2 + 2.