Problem Description

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.

Input Format

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

Output Format

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$).

4

48

Hint

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