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

Input

Output

8

8

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