Bugatti

After becoming CEO of Hoptiver, Andy is now a millionare! Unsure what to do with all his newfound wealth, Andy decides to buy a Bugatti like his favourite influencer.

However, in his infinite wealth Andy only owns banknotes worth multiples of million dollars. Andy wonders, with how many different combinations of his $n$ denominations of bank notes could he buy a Bugatti of cost $k$ million dollars.

Input Format

The input will consist of two lines. The first line has two space-separated integers, $n$ and $k$. The following line consists of $n$ integers, the $ith$ of which represents the value of his $ith$ type of bank note, in millions of dollars. These values will be distinct.

Output Format

The output should consist of a single integer, representing the number of combinations. Since there could be many combinations, output this value modulo 1e9+7.

Sample Input

3 5
1 2 3

Sample Output

5

Sample Explanation

The combinations that sum to $5$ million dollars are $1+1+1+1+1$, $1+1+1+2$, $1+1+3$, $1+2+2$ and $2+3$.

Constraints

$1 \le n \le 50$

$1 \le a[i] \le 50$. That is, the value of each bank note is between 1 and 50 million dollars.

$1 \le k \le 1e5$