Xiao Hai is very interested in military affairs, so today she found a military game to play.

In the game, Xiao Hai's soldiers have $n$ outposts, labeled $1, \dots, n$. To develop the economy, Xiao Hai built many paths between the outposts. Specifically, for any outpost $i$ with a label other than $1$, Xiao Hai built a bidirectional road of length $1$ connecting $i$ and $\frac{i}{h(i)}$, where $h(i)$ is defined as the smallest prime factor of $i$. (It is not difficult to prove that all outposts will form a tree.)

To protect national security, Xiao Hai decided to have soldiers patrol between all pairs of points every day. Of course, patrolling also requires a certain cost; specifically, the cost of patrolling between outpost $i$ and outpost $j$ is the shortest distance between the two points.

Now, Xiao Hai wants to know the total cost of patrolling each day. Since the answer is too large, you only need to output the result modulo $10^9+7$.

Specifically, Xiao Hai wants to know: $$ \sum_{i=1}^{n-1}\sum_{j=i+1}^ndis(i,j)\pmod{ 10^9+7} $$ where $dis(i,j)$ denotes the shortest distance between $i$ and $j$ in this tree.

Input

A single line containing an integer $n$, representing the number of outposts.

Output

A single line containing an integer, representing the sum of the shortest distances between all pairs of points in the tree.

Examples

Input 1

6

Output 1

31

Input 2

50

Output 2

4986

Constraints

For $100\%$ of the data: $n \le 10^{10}$