CT35437

Sahil's Tender Ways Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the coastal hub of Tidewater with crates of stairwells, and Sahil the archivist must account for every last one. 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: 2393 21 3 46 85 98 139 202 212 220 222 230 241 323 360 365 408 410 414 429 452 470 496
Output: 14287670

Example 2:

Input: 2533 21 53 94 120 169 178 181 216 217 227 231 235 257 271 288 333 353 359 394 409 440 461
Output: 771427

Example 3:

Input: 281 21 71 100 106 117 122 141 149 162 174 189 233 273 279 308 316 332 336 390 407 442 498
Output: 0

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Sahil's Tender Ways Ledger - MEDIUM Coding Problem | CodeTikki