CT35810

Bhanu's Violet vaults

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Bhanu inherited the lighthouse at the gull cliffs of Screech Point along with its curious bookkeeping system for vaults. 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 <= 4000; 1 <= n <= 30; 1 <= coin <= 10^4.

Example 1:

Input: 3401 13 11 30 40 78 147 185 225 231 240 280 304 348 369
Output: 46503961

Example 2:

Input: 3157 13 3 40 90 91 148 185 241 293 344 423 473 474 487
Output: 7733153

Example 3:

Input: 3131 13 14 23 33 34 53 84 182 254 258 354 368 454 486
Output: 167315021

Constraints:

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

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