CT35533

The Vermilion runs of Quinn

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the acacia flats of Thornveld, Quinn records each runs in a worn leather ledger. The guild wants answers, not guesses. 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: 620 22 27 76 86 133 135 157 168 180 208 266 272 294 299 307 310 318 324 325 339 435 436 491
Output: 36

Example 2:

Input: 1896 22 23 40 47 53 56 78 141 168 170 213 224 230 313 329 361 376 394 434 440 463 478 479
Output: 6841471

Example 3:

Input: 1568 22 38 68 74 84 101 111 229 237 297 308 318 325 326 353 354 361 372 414 432 439 482 489
Output: 30320

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Vermilion runs of Quinn - MEDIUM Coding Problem | CodeTikki