Loading...
Loading...
Loading...
Arjun collects the fee for a class trip and must pay the bus driver exactly amount rupees. He has coins of n different values, as many of each as he needs.
Two payments are the same when they use the same number of coins of each value, in any order. So 1 + 2 and 2 + 1 are one payment. Print how many different payments make exactly the amount, modulo 10^9 + 7. Print 0 if there is none.
Example 1
Input
3 1 2 5 5
Output
4
The payments are 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1, so the answer is 4.
Example 2
Input
1 2 3
Output
0
Only 2-rupee coins cannot make an odd amount.
Try the problem first. Open one hint at a time.
Let ways[a] be the number of payments that make a with the coins looked at so far. ways[0] = 1.
Take the coins one value at a time. For each value c, every amount a from c upward gains ways[a - c]: the payments that add one more c.
Keep the coin loop outside and the amount loop inside. The other order counts 1 + 2 and 2 + 1 as two payments.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor