Ordered Coin Combinations

You are given \(n\) types of coins with distinct denominations \(a_i\) (for \(1 \le i \le n\)) and an infinite supply of each. You need to pay an amount \(w\). Determine the number of ways to pay exactly \(w\) using these coins. Note that the order in which the coins are used matters. For example, for \(w = 3\) using a \(1\) coin and a \(2\) coin, the sequences \(1+2\) and \(2+1\) are considered different. The answer should be computed modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(w\), denoting the number of coin types and the target amount, respectively. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the denominations of the coins.

outputFormat

Output a single integer: the number of ways to form the amount \(w\) using the coins, modulo \(10^9+7\).

sample

3 5
1 2 5

9