Problem Background

You are a very wealthy child.

Note: This problem has a slightly different input format compared to the corresponding problem in the Advanced section.

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$. How many combinations of banknotes can exactly pay the amount $w$? The answer should be taken modulo $10^9+7$.

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 combinations of banknotes that can exactly pay the amount $w$.

Sample Input and Output

Sample Input #1

6 15
1 5 10 20 50 100

Sample Output #1

6

Sample Input #2

3 15
1 5 11

Sample Output #2

5

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$.

In reality, the child is not actually wealthy.

见题面 Input 部分

见题面 Output 部分