CT35261

Mina's Tender Ways Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the cinnabar mines of Vermilion with crates of runs, and Mina the reckoner must account for every last one. 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 <= 4000; 1 <= n <= 30; 1 <= coin <= 10^4.

Example 1:

Input: 2973 27 11 37 57 112 125 137 139 140 150 153 158 177 222 283 284 298 309 312 328 370 416 421 444 445 459 469 493
Output: 920999699

Example 2:

Input: 2387 27 27 56 92 101 109 116 130 185 186 193 209 214 293 302 327 337 349 398 400 401 403 405 443 476 477 489 498
Output: 17672818

Example 3:

Input: 108 27 25 45 58 70 81 138 146 150 164 177 239 241 263 265 268 285 300 315 347 350 373 414 425 463 470 494 496
Output: 1

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Mina's Tender Ways Ledger - MEDIUM Coding Problem | CodeTikki