Description

After passing numerous written tests and interviews, Xiaoming successfully joined Macrohard Company.

Today, Xiaoming's task is to fill in a table with the following specifications:

The table has n rows and n columns, with both row and column indices starting from 1.

The value of the element in the i-th row and j-th column is the square of gcd(i, j), where gcd denotes the greatest common divisor. Below is an example of the first four rows and columns of such a table:

1  1  1  1
1  4  1  4
1  1  9  1
1  4  1 16

Suddenly, Xiaoming had a peculiar idea—he wanted to know the sum of all elements in this table.

Given the enormous size of the table, he hopes to leverage the power of computers to solve this problem.

Input Format

A single line containing a positive integer n, as described in the problem.

For 30% of the data, n <= 1000

There exists 10% of the data where n = 10^5

For 60% of the data, n <= 10^6

For 100% of the data, n <= 10^7

Output Format

A single line containing the sum of all elements in the table. Since the answer may be very large, please output the result modulo (10^9 + 7) (i.e., one billion and seven).

```output1
48

Source

2018 9th Lanqiao Cup C/C++ Group B National Finals Real Questions