M. The Smartest at ASZoo
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Corvus the Crow, ASZoo's resident genius, loves tackling number-theory puzzles.

In this problem, Corvus is given a positive integer $$$n$$$ and must count how many unordered pairs of distinct numbers between $$$1$$$ and $$$n$$$ are coprime, The number could be very large, so print it modulo $$$1 000 000 007$$$.

A pair $$$(i,j)$$$ with $$$1 \le i \lt j \le n$$$ is called coprime if $$$\gcd(i,j) = 1$$$. Compute the total number of such pairs.

Input

The only integer in the input is $$$n$$$, ($$$2 \le n \le 10^{11}$$$).

Output

Print the answer.

Examples
Input
100
Output
3044
Input
59
Output
1086
Input
1765
Output
947722