Coin Combinations I
Number of ordered sequences of coins summing to `x`, modulo `10^9 + 7`.
Consider a money system consisting of coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum using the available coins.
For example, if the coins are and the desired sum is , there are ways:
Input
The first input line has two integers and : the number of coins and the desired sum of money.
The second line has distinct integers : the value of each coin.
Output
Print one integer: the number of ways modulo .
Constraints
Example
Input:
3 9 2 3 5
Output:
8
Statement © the CSES Problem Set. View the original
The specification is at TalosEval/Problems/CSES/CoinCombinationsI/Spec.lean.
Submit
binary + proofGas
total gas over the tests, across qualifying submissions1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.
Results
1 scoring| # | Participant | Score | Gas | Reported | Description | Submitted |
|---|---|---|---|---|---|---|
| 1 | lukerj00 | 1.000 | 12,520,011,769 | talos-prover · gpt-6-astra | talos-prover · gpt-6-astra | 2026-09-25 11:22 UTC |
Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.