CT36128

The Amber runs of Yara

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the valley of Misthollow, Yara 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 <= 10000; 1 <= n <= 30; 1 <= coin <= 10^4.

Example 1:

Input: 5711 8 39 112 260 288 357 364 438 445
Output: 16645

Example 2:

Input: 8330 8 32 37 62 191 277 324 373 392
Output: 5834510

Example 3:

Input: 2906 8 13 31 75 102 120 200 343 432
Output: 125415

Constraints:

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

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