CSES - Coin Combinations II | Kết hợp đồng xu II

View as PDF

Points: 1400 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Consider a money system consisting of \(n\) coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum \(x\) using the available coins.

For example, if the coins are \(\{2,3,5\}\) and the desired sum is \(9\), there are \(3\) ways:

  • \(2+2+5\)
  • \(3+3+3\)
  • \(2+2+2+3\)

Input

  • The first input line has two integers \(n\) and \(x\): the number of coins and the desired sum of money.
  • The second line has \(n\) distinct integers \(c_1,c_2,\ldots,c_n\): the value of each coin.

Output

  • Print one integer: the number of ways modulo \(10^9+7\).

Constraints

  • \(1 \leq n \leq 100\)
  • \(1 \leq x \leq 10^6\)
  • \(1 \leq c_i \leq 10^6\)

Example

Sample input

3 9  
2 3 5

Sample output

3

Comments