At Last, Coprime

Time limit5sMemory limit1024 MB

Summary

Given N up to 10^11, sum i+j over all pairs (i, j) with 1 to N that are coprime, and output the result modulo 10^9+7.

Level: Hard8 of 10
Topics: Math, Number theory, Divide and conquer
Solved: No attempts yet

Problem

Given a positive integer $N$ .

For every pair of positive integers $(i, j)$ with both components at most $N$ and $\gcd(i, j)=1$ , add the sum of its components. Compute the value of the expression below.

$\sum_{i=1}^{N}\sum_{j=1}^N{\left( i+j \right) I\left\{ \gcd\left( i,j \right) =1 \right\}}$

$I\left\{ condition \right\}$ is the Indicator Function, which returns $1$ when $condition$ is true and $0$ otherwise.

Input

The first line contains an integer $N(1\le N\le 10^{11})$ .

Output

Print the total of the component sums over all coprime pairs, which is the value of the expression above. Since the answer can be very large, print the remainder when it is divided by $10^9+7$ .

Examples5

Example 1
Input
```
1
```
Expected output
```
2
```
Example 2
Input
```
3
```
Expected output
```
26
```
Example 3
Input
```
1000
```
Expected output
```
608612156
```
Example 4
Input
```
1000000
```
Expected output
```
969057749
```
Example 5
Input
```
1000000000
```
Expected output
```
895661967
```