CT37994

Gautam and the Wild stairwells

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Gautam runs the ferry office at the marble forum of Argentium. Today the books show a list of stairwells, and the numbers must be worked out before sundown. Task: Coins of n given sizes may be used without limit. Print the number of combinations summing to amount (order does not matter) mod 1000000007. Input format: First line: amount and n. Second line: n distinct coin sizes. Output format: Print the count mod 1000000007. Constraints: 0 <= amount <= 2000; 1 <= n <= 30; 1 <= coin <= 10^4.

Example 1:

Input: 592 9 72 116 168 191 276 283 289 379 428
Output: 1

Example 2:

Input: 1663 9 20 29 121 131 155 275 331 344 490
Output: 1983

Example 3:

Input: 63 9 63 88 220 240 247 316 323 342 434
Output: 1

Constraints:

0 <= amount <= 2000; 1 <= n <= 30; 1 <= coin <= 10^4.

Loading...
Test Cases:No test cases
No test cases available.
Gautam and the Wild stairwells - MEDIUM Coding Problem | CodeTikki