409063: GYM103428 I Distance

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$$$.

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

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

5

104

10

666

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