Background

You are a very rich kid.

Note: This problem is the corresponding one in the “Advanced” section, but the input format is slightly different.

Problem Description

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

Input Format

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 Format

Output one integer, representing the number of banknote combinations that can form exactly $w$.

6 15
1 5 10 20 50 100

6

3 15
1 5 11

5

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

Translated by ChatGPT 5