There are n types of coins in Gensokyo. The ith type is worth Ai. 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 Ai. It is guaranteed that no 2 coin types worth the same.
### Output
- Print one integer, the number of ways modulo 109+7.
### Constraints
- 1≤n≤1000.
- 1≤k≤105.
- 1≤Ai≤105.
### Example
Input:
34123
Output:
4
Note: There are 4 ways:
- 1+1+1+1
- 1+1+2
- 1+3
- 2+2