Counting in Binary, Glued Together

Medium

A counter writes the numbers 1, 2, 3, …, last in binary one after another, with no separators and no leading zeros, producing one long string of zeros and ones. Read that string as a binary number and return its value modulo 10⁹ + 7.

Example 1

last=2 → 6

In binary, 1 is 1 and 2 is 10. Glued together they give 110, which is 6.

Example 2

last=5 → 1765

1 + 10 + 11 + 100 + 101 = 11011100101, which is 1765.

Example 3

last=1 → 1

Just 1, so the answer is 1.

Constraints

1 ≤ last ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Math Simulation

Similar problems

Sum of Binary Strings Easy A String That Copies Itself Easy Division Without Dividing Medium Multiplying Digit Strings Medium Mirrored One-Bit Codes Medium

Input

last=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 31 tests on the server, hidden ones included.