I. Distance
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Moon has learned the Hasse Diagram in his math course. Therefore, he draws an undirected graph with $$$n$$$ nodes indexed $$$1,2,\cdots,n$$$ and adds some edges between node $$$x$$$ and node $$$y$$$ if $$$x|y$$$ and $$$\frac{y}{x}$$$ is a prime while the weight of the edge is $$$\frac{y}{x}$$$.

Moon wants to know the value of $$$\sum_{i=1}^{n}\sum_{j=1}^{n}dis(i,j)$$$, where $$$dis(x,y)$$$ means the shortest distance between node $$$x$$$ and node $$$y$$$. Since the answer will be very large, you should print the answer modulo $$$10^9+7$$$.

Input

The only line contains an integer $$$n$$$. ($$$1\leq n \leq 10^{11}$$$)

Output

The only line contains an integer, indicating the answer modulo $$$10^9+7$$$.

Examples
Input
5
Output
104
Input
10
Output
666
Note

$$$A|B$$$ means $$$A$$$ is one factor of $$$B$$$.