P2834 Banknote Problem 3

You are a very rich kid. **Note:** This problem is the corresponding one in the “Advanced” section, but the input format is slightly different.

You have $n$ types of banknotes with distinct denominations. The denomination of the $i$-th type is $a_i$, and you have unlimited banknotes of each type. Now you need to pay an amount of $w$. How many different combinations of banknotes can pay exactly $w$? Output the answer modulo $10^9+7$.

The first line contains two positive integers $n, w$, representing the number of types of banknotes and the amount to be formed. 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, representing the number of banknote combinations that can form exactly $w$.

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 rich. Translated by ChatGPT 5