재현이는 다음과 같은 소스를 작성했다.</p>

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;
}

n이 큰 경우에 위의 소스를 그대로 실행하면 시간초과가 난다.

n이 주어졌을 때, all_pair_lcm(n)을 리턴값을 출력하는 프로그램을 작성하시오.

lcm(i, j)는 i와 j의 최소공배수를 구하는 함수이다.

입력 형식

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 10⁶)

출력 형식

첫째 줄에 all_pair_lcm(n)을 리턴값을 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

5

예제 출력 2

81

예제 입력 3

10

예제 출력 3

1036

예제 입력 4

25

예제 출력 4

38682