One day, you discover a magical function $f(x)$ that satisfies several magical properties:

1. $f(1)=1$.
2. $f(p^c)=p \oplus c$ (where $p$ is a prime number and $\oplus$ denotes the bitwise XOR operation).
3. $f(ab)=f(a)f(b)$ (where $a$ and $b$ are coprime).

After seeing this function, you are very excited and want to calculate $\sum\limits_{i=1}^n f(i)$.

Since this number can be very large, you only need to output $\sum\limits_{i=1}^n f(i) \bmod (10^9+7)$.

Input

A single integer $n$.

Output

A single integer representing $\sum\limits_{i=1}^n f(i) \bmod 1000000007$.

Examples

Input 1

6

Output 1

16

Input 2

233333

Output 2

179004642

Input 3

9876543210

Output 3

895670833

Subtasks

For $30\%$ of the data, $n \leq 100$.

For $60\%$ of the data, $n \leq 10^6$.

For $100\%$ of the data, $1 \leq n \leq 10^{10}$.