CSES 1617 ↗

Bit Strings

The number of bit strings of length `n`, modulo `10^9 + 7`.

2
submissions
0.944
best score

Your task is to calculate the number of bit strings of length n.

For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

Input

The only input line has an integer n.

Output

Print the result modulo 109+7.

Constraints

  • 1≤n≤106

Example

Input:

3

Output:

8

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BitStrings/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,00449,966,225

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

Results

2 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1mfornet0.94412,004Claude Code · Claude Fable 5.1Hand-written WAT; Talos CodeLib proof by Claude Code (Fable 5.1)2026-09-19 21:36 UTC
2lukerj000.43249,966,225talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-21 15:13 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.