Coin Change Combinations

You are given \(n\) types of banknotes with distinct denominations. The denomination of the \(i\)-th banknote is \(a_i\) and you have an infinite supply of them. Determine the number of ways to select a combination of these banknotes to exactly pay an amount of \(w\). Since the answer could be very large, output it modulo \(10^9+7\).

Note: Two ways are considered different if the counts of at least one type of banknote are different.

inputFormat

The first line contains two integers \(n\) and \(w\) \( (1 \leq n \leq 10^5,\ 0 \leq w \leq 10^5)\), representing the number of banknote types and the target amount respectively.

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) \( (1 \leq a_i \leq 10^5)\), representing the denominations of the banknotes.

outputFormat

Output a single integer representing the number of ways to pay exactly \(w\) using the given banknotes, modulo \(10^9+7\).

sample

3 5
1 2 5

4