Description

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

Today, Xiao Ming's task is to fill out a table:

The table has n rows and n columns, with both row and column numbering 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 are the first four rows and columns of this table:

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

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

Since the table is too large, he hopes to leverage the power of computers.

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. Since the answer may be very large, please output the result modulo (10^9 + 7) (i.e., one billion and seven).

```output1
48

Translation

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