CT35317

The Tender Ways Beneath Thimblewick

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the wren hedges of Thimblewick opens only for a perfect tally of stairwells. Amara means to find out. 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 <= 10000; 1 <= n <= 30; 1 <= coin <= 10^4.

Example 1:

Input: 7606 30 1 13 36 39 44 46 120 134 152 175 197 199 211 214 221 223 250 281 326 329 334 344 353 375 395 403 437 455 471 489
Output: 815842699

Example 2:

Input: 5789 30 18 24 54 64 90 106 107 113 132 165 167 169 171 186 210 243 244 283 286 323 352 367 369 376 390 395 440 460 471 474
Output: 476805931

Example 3:

Input: 8672 30 47 49 67 76 83 86 96 107 145 150 177 217 225 273 294 333 340 359 360 370 378 414 427 428 429 451 463 477 493 499
Output: 260060770

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Tender Ways Beneath Thimblewick - MEDIUM Coding Problem | CodeTikki