-->

12/1/20

Coin Combinations I CSES dynamic programming problem set solution

 Coin Combinations I CSES dynamic programming problem set solution -

Problem statement-
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct 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 8 ways:
  • 2+2+5
  • 2+5+2
  • 5+2+2
  • 3+3+3
  • 2+2+2+3
  • 2+2+3+2
  • 2+3+2+2
  • 3+2+2+2
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 c1,c2,,cn: the value of each coin.

Output

Print one integer: the number of ways modulo 109+7.

Constraints
  • 1n100
  • 1x106
  • 1ci106
Example

Input:
3 9
2 3 5


Output:
8

Code Solution -



Advertiser

all right reserved @technicalkeeda.in. Powered by Blogger.