CT37453

The Tender Ways of the Shimmering vaults

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the zephyr cliffs of Galeholm opens only for a perfect tally of vaults. Kate 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: 969 10 50 155 173 177 202 293 298 372 382 405
Output: 8

Example 2:

Input: 1162 10 57 62 105 107 108 137 317 434 483 496
Output: 162

Example 3:

Input: 1341 10 80 89 148 185 214 221 275 338 349 370
Output: 59

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 the Shimmering vaults - MEDIUM Coding Problem | CodeTikki