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

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

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

Input

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

Output

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

Sample

InputOutput
8
8

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


Discussion

Statistics


64% Solution Ratio

UshanGhoshEarliest, 1M ago

fakhrulsojibFastest, 0.0s

fakhrulsojibLightest, 131 kB

MatrixShortest, 204B

Submit

Login to submit

Editorial

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

Toph uses cookies. By continuing you agree to our Cookie Policy.