LCM(i, j)

재현이는 다음 소스를 작성했다.

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)는 i와 j의 최소공배수를 구하는 함수다. n이 크면 이 이중 반복문은 시간 안에 끝나지 않는다.

n이 주어졌을 때 all_pair_lcm(n)의 반환값을 출력하는 프로그램을 작성하시오. 즉 $1 \le i < j \le n$을 만족하는 모든 쌍 $(i, j)$에 대해 $\operatorname{lcm}(i, j)$를 더한 뒤, 그 합을 $10^9 + 7$로 나눈 나머지를 구한다.

첫째 줄에 n이 주어진다. ($1 \le n \le 10^6$)

첫째 줄에 all_pair_lcm(n)의 반환값을 출력한다.