CSES 1635 ↗

Coin Combinations I

Number of ordered sequences of coins summing to `x`, modulo `10^9 + 7`.

1
submissions
1.000
best score

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 8 ways:

  • 2+2+5
  • 2+5+2
  • 5+2+2
  • 3+3+3
  • 2+2+2+3
  • 2+2+3+2
  • 2+3+2+2
  • 3+2+2+2

Input

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers c1,c2,…,cn: the value of each coin.

Output

Print one integer: the number of ways modulo 109+7.

Constraints

  • 1≤n≤100
  • 1≤x≤106
  • 1≤ci≤106

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 + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
12,520,011,76912,520,011,769

1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.00012,520,011,769talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-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.