Harddprecursionmath
Coin Change: Number of Ways
Time limit 2 s · Memory 64 MBAcceptance: 100.0%Solved by: 1
Statement
The first line contains n, the number of coin types; the second line contains n distinct denominations; the third line contains the amount S. Print the number of ways to make S using the coins; every denomination may be used any number of times and order does not matter (1+2 and 2+1 are the same way). Print the answer modulo 10^9 + 7.
Examples
Example 1
Input
3 1 2 5 5
Output
4
Example 2
Input
1 2 3
Output
0
Constraints
- 1 ≤ n ≤ 50
- 1 ≤ denomination ≤ 1000
- 0 ≤ S ≤ 10^4