Problem Background

jjh loves lattices.

Problem Description

jjh has a square lattice with the bottom-left corner at $(1,1)$ and the top-right corner at $(n,n)$.

jjh also has a line described by the equation $y = kx$, where $k \in (0, \infty)$.

For any given $k$, let the line pass through $cnt$ points in the lattice. jjh has a fondness level for this line, which is $cnt^2$.

jjh wants to know the sum of the fondness levels for all possible lines modulo $10^9 + 7$. Please help jjh find this result.

Input Format

A single line containing an integer $n$.

Output Format

Output a single integer, representing the sum of the fondness levels modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

2

Sample Output #1

6

Sample Input #2

1919810

Sample Output #2

107114211

Notes

Sample Explanation #1

When $k$ is $\frac{1}{2}$, the line passes through the point $(2,1)$ in the lattice, and the fondness level is $1^2 = 1$. When $k$ is $1$, the line passes through the points $(1,1)$ and $(2,2)$, and the fondness level is $2^2 = 4$. When $k$ is $2$, the line passes through the point $(1,2)$, and the fondness level is $1^2 = 1$. The sum of the fondness levels is $1 + 4 + 1 = 6$.

Data Range

This problem uses subtask testing.

For $100\%$ of the data, $1 \le n \le 2^{31} - 1$.

见题面 Input 部分

见题面 Output 部分