CT36099

Alaric and the Tender Ways

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the seal rocks of Barking Cove; Alaric weighs the day's runs manifests and starts the calculations. 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: 456 30 24 63 73 90 101 123 126 144 147 161 167 213 217 234 241 259 263 300 343 352 357 412 427 428 446 447 465 479 494 498
Output: 55

Example 2:

Input: 2519 30 32 48 54 87 94 107 112 119 125 130 174 196 201 215 230 241 261 276 293 300 327 330 380 387 390 404 430 461 474 489
Output: 73964623

Example 3:

Input: 2727 30 33 61 66 69 73 76 81 106 118 128 137 142 152 169 205 230 234 237 243 251 273 281 325 326 363 389 439 446 479 497
Output: 366978928

Constraints:

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

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