最大公约数之和

题目描述:

给定 \(n\)，求
$$ \sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j) $$

其中 \(\gcd(i, j)\) 表示 \(i\) 和 \(j\) 的最大公约数。

输入格式:

输入包含多组数据，每组数据占一行，包含一个正整数n。
输入结束的标志为n = 0。

输出格式:

对于每组数据，输出一行，即所求和。
答案对10⁹ + 7取模。

样例输入:

10
100
200000
0

样例输出:

67
13015
295492159

提示:

对于100%的数据，输入包含不超过100组数据，2 ≤ n ≤ 4 * 10⁶。

时间限制: 2000ms
空间限制: 256MB

---