CT38619

The Opal ledgers of Jace

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the lily shoals of Padmore, Jace studies rows of ledgers entries. One clean number will settle the guild's oldest argument. 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 <= 2000; 1 <= n <= 30; 1 <= coin <= 10^4.

Example 1:

Input: 1995 28 1 31 72 83 85 87 108 111 126 131 149 155 170 189 202 211 231 244 247 298 340 377 380 397 408 411 422 430
Output: 744592706

Example 2:

Input: 1579 28 3 43 48 65 109 118 127 128 204 208 233 244 267 275 277 311 322 331 333 346 373 378 381 417 447 453 457 469
Output: 7348204

Example 3:

Input: 1175 28 6 38 41 90 103 146 147 158 167 186 197 206 207 226 234 241 243 246 254 289 313 355 382 403 410 437 449 475
Output: 356687

Constraints:

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

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