P8670 [Lanqiao Cup 2018 National B] Matrix Sum

After passing many written tests and interviews, Xiao Ming successfully joined Macrohard. Today, Xiao Ming's task is to fill in a table like this: The table has $n$ rows and $n$ columns, and both row and column indices start from $1$. The value of the element in row $i$ and column $j$ is the square of $\gcd(i, j)$, where $\gcd$ means the greatest common divisor. Below are the first four rows and first four columns of the table: ``` 1 1 1 1 1 4 1 4 1 1 9 1 1 4 1 16 ``` Xiao Ming suddenly had a strange idea. He wants to know the sum of all elements in this table. Since the table is too large, he hopes to use the power of a computer.

One line with one positive integer $n$, as described in the problem.

One line with one number, the sum of all elements. Since the answer is large, output the result modulo $1000000007$ (i.e. $10^9+7$).

For $30\%$ of the testdata, $n \le 1000$. There is $10\%$ of the testdata where $n = 10^5$. For $60\%$ of the testdata, $n \le 10^6$. For $100\%$ of the testdata, $n \le 10^7$. Translated by ChatGPT 5