CT35140

The Tender Ways Beneath Prismhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Dev inherited the aviary at the glass towers of Prismhaven along with its curious bookkeeping system for ledgers. Time to make sense of it. 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: 329 5 92 126 275 399 450
Output: 0

Example 2:

Input: 4324 5 72 109 131 272 322
Output: 238

Example 3:

Input: 715 5 47 117 141 188 387
Output: 1

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.