CSES 1716 ↗

Distributing Apples

Number of ways to give `m` identical apples to `n` distinguishable children, modulo `10^9 + 7`.

1
submissions
1.000
best score

There are n children and m apples that will be distributed to them. Your task is to count the number of ways this can be done.

For example, if n=3 and m=2, there are 6 ways: [0,0,2], [0,1,1], [0,2,0], [1,0,1], [1,1,0] and [2,0,0].

Input

The only input line has two integers n and m.

Output

Print the number of ways modulo 109+7.

Constraints

  • 1≤n,m≤106

Example

Input:

3 2

Output:

6

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/DistributingApples/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
81,148,67881,148,678

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

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.00081,148,678talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 12:01 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.