Problem Background

You are a very wealthy child.

Problem Description

You have $n$ types of banknotes with distinct denominations. The denomination of the $i$-th type of banknote is $a_i$ and you have an unlimited supply of each. You need to pay an amount of $w$. Determine how many ways there are to pay the amount $w$, modulo $10^9+7$.
Note that different sequences of the same combination of banknotes are considered different ways. For example, paying $3$ with a $1$ banknote and a $2$ banknote results in two ways ($1+2$ and $2+1$).

Input Format

The first line contains two positive integers $n$ and $w$, representing the number of types of banknotes and the amount to be paid, respectively.
The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, separated by spaces, representing the denominations of the $n$ types of banknotes.

Output Format

A single integer on one line, representing the number of ways to pay the amount, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

6 15
1 5 10 20 50 100

Sample Output #1

42

Sample Input #2

3 15
1 5 11

Sample Output #2

39

Notes

For $40\%$ of the test cases, $n \le 10$ and $w \le 100$.
For $100\%$ of the test cases, $1 \le n \le 10^3$ and $1 \le a_i \le w \le 10^4$.

Actually, the child is not that wealthy.

见题面 Input 部分

见题面 Output 部分