Background

You are a very rich kid.

Problem Description

You have $n$ types of banknotes with pairwise distinct denominations. The $i$-th type has denomination $a_i$, and there are infinitely many banknotes of each type. Now you need to pay an amount of $w$. Find how many ways there are to pay exactly $w$, and output the answer modulo $10^9+7$.

Note that here, the same multiset of banknotes is considered different if the payment order is different. For example, to pay $3$, using one banknote of value $1$ and one banknote of value $2$ produces two ways ($1+2$ and $2+1$).

Input Format

The first line contains two positive integers $n, w$, representing the number of banknote types and the target amount.

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

Output one integer per line, representing the number of payment ways.

6 15
1 5 10 20 50 100

42

3 15
1 5 11

39

Hint

For $40\%$ of the testdata, $n \le 10$ and $w \le 100$.

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

In fact, the kid is not that rich.

Translated by ChatGPT 5