CT35483

The Tender Ways of Chessfield

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the rook towers of Chessfield opens only for a perfect tally of ledgers. Parth 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 <= 2000; 1 <= n <= 30; 1 <= coin <= 10^4.

Example 1:

Input: 1388 26 6 23 33 37 38 74 83 85 108 159 172 175 198 240 245 270 306 319 330 356 385 454 482 489 493 497
Output: 48860976

Example 2:

Input: 657 26 6 7 13 54 56 66 67 118 188 196 199 201 204 211 269 291 319 352 363 370 395 419 420 436 450 488
Output: 162857

Example 3:

Input: 1262 26 61 66 75 91 114 127 139 158 167 174 211 234 245 272 285 286 294 344 363 379 396 437 455 460 480 490
Output: 16351

Constraints:

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

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