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 <= 10$), the number of testcases.
Each testcase starts with a line consisting of two integers $n, m$ ($1 <= n <= 100$, $1 <= m <= 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 <= c_i <= 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$.
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*.
## Input
The first line contains a positive integer $T$ ($T <= 10$), the number of testcases.Each testcase starts with a line consisting of two integers $n, m$ ($1 <= n <= 100$, $1 <= m <= 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 <= c_i <= 10000$), the coin values.
## Output
For each testcase, output a single line consisting of the number of ways to give exactly $m$ dollar change, module $10^9 + 7$.
[samples]
## Note
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*.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ denote the number of coin types.
- Let $ m_k \in \mathbb{Z} $ denote the target change amount.
- Let $ C_k = (c_{k,0}, c_{k,1}, \dots, c_{k,n_k-1}) $ be a sequence of positive integers representing coin values.
**Constraints**
1. $ 1 \le T \le 10 $
2. For each $ k \in \{1, \dots, T\} $:
- $ 1 \le n_k \le 100 $
- $ 1 \le m_k \le 10000 $
- $ 1 \le c_{k,i} \le 10000 $ for all $ i \in \{0, \dots, n_k - 1\} $
**Objective**
For each test case $ k $, compute the number of non-negative integer solutions $ (x_0, x_1, \dots, x_{n_k-1}) $ to:
$$
\sum_{i=0}^{n_k-1} x_i \cdot c_{k,i} = m_k
$$
Output the result modulo $ 10^9 + 7 $.