Lucky Number Seven

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.