cho.sh

LCM(i, j)

Add the least common multiple over every pair i<j up to n and print the remainder modulo 1,000,000,007.

Medium7Number theoryMathPrefix sumNo attempts yetTime limit1sMemory limit256 MB

Problem

Jaehyun wrote the source below.

long long mod = 1000000007;
long long all_pair_lcm(int n) {
    long long ans = 0;
    for (int i=1; i<=n-1; i++) {
        for (int j=i+1; j<=n; j++) {
            ans += lcm(i, j);
            ans %= mod;
        }
    }
    return ans;
}

lcm(i, j) returns the least common multiple of i and j. When n is large, this double loop does not finish in time.

Given n, write a program that prints the return value of all_pair_lcm(n). That is, add lcm⁡(i,j)\operatorname{lcm}(i, j) over every pair (i,j)(i, j) with 1≤i<j≤n1 \le i < j \le n, then print the remainder of that sum divided by 109+710^9 + 7.

Input

The first line contains n. (1≤n≤1061 \le n \le 10^6)

Output

Print the return value of all_pair_lcm(n) on the first line.