CSES 2064 ↗

Bracket Sequences I

Number of balanced bracket sequences of length `n`, modulo `10^9 + 7`.

1
submissions
1.000
best score

Your task is to calculate the number of valid bracket sequences of length n. For example, when n=6, there are 5 sequences:

  • ()()()
  • ()(())
  • (())()
  • ((()))
  • (()())

Input

The only input line has an integer n.

Output

Print the number of sequences modulo 109+7.

Constraints

  • 1≤n≤106

Example

Input:

6

Output:

5

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BracketSequencesI/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
26,204,78826,204,788

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

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.00026,204,788talos-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.