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~