# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Lucky Number Seven

By ishtupeed · Limits 1s, 512 MB

People often consider the number $7$ as lucky. “But why?” - you might ask. Well, consider the fact that if we convert the number $7$ into base-2, we get $111$. Again, if we convert it to base-6, we get $11$. That means, on at least two bases ($b>1$), the number $7$ can be represented only using $1$.

Now you must be thinking - “Then why stop at $7$? Why not other numbers as well?” To that, I say, “Sure! Why not?”.

If a positive integer can be represented only using $1$ in at least two bases ($b>1$), we will call it lucky. In this problem, your task is to find the sum of all the lucky numbers less than $N$.

## Input

The input consists of a single integer $\left(1 < N \leq 10^{12}\right)$. $N$ is in base-10.

## Output

Print a single integer denoting the sum. As the answer can be large, print the answer modulo $10^9+7$.

## Sample

InputOutput
8

8


There are two numbers below 8 that are lucky: $\{1, 7\}$. So the result is $(1 + 7) \mod (10^9 + 7) = 8$.

### Statistics

64% Solution Ratio

UshanGhoshEarliest, 1M ago

fakhrulsojibFastest, 0.0s

fakhrulsojibLightest, 131 kB

MatrixShortest, 204B

### Editorial

Trivial Case 1 111 will be represented using 111 for all base b≥2b \geq 2b≥2. Trivial Case 2 222 is ...