There are $n$ types of coins in Gensokyo. The $i^{th}$ type is worth $A_i$. Marisa has to pay a debt of $k$, how many **ordered** ways of choosing coins to produce $k$?
### Input
- The first line contains 2 integers $n, k$.
- The second line contains $n$ distinct integers $A_i$. It is guaranteed that no 2 coin types worth the same.
### Output
- Print one integer, the number of ways modulo $10^9+7$.
### Constraints
- $1 \le n \le 1000$.
- $1 \le k \le 10^5$.
- $1 \le A_i \le 10^5$.
### Example
Input:
```
3 4
1 2 3
```
Output:
```
4
```
Note: There are $4$ ways:
- $1 + 1 + 1 + 1$
- $1 + 1 + 2$
- $1 + 3$
- $2 + 2$
