P2840 Banknote Problem 2

You are a very rich kid.

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

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 one integer per line, representing the number of payment ways.

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