Coin Change (Number of Ways)

Medium#dynamic-programming· solved by 0 · time limit 2.0 s

In how many ways can you make $x$ using unlimited coins of the given distinct values? Order doesn't matter (1+2 and 2+1 are the same). Print modulo $10^9+7$ .

Input

$n$ , the $n$ distinct coin values, then $x$ .

Output

The number of ways modulo 1000000007.

Constraints

$1 \le n \le 100$ , $0 \le x \le 10^4$

Sample 1

Input

3
1 2 5
5

Output

Sample 2

Input

1
2
3

Output