Background

se likes lattices.

Problem Description

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

se also has a line with equation $y=kx$, where $k\in(0,\infty)$.

For any $k$, suppose the line passes through $cnt$ lattice points. se's preference value for this line is $cnt^2$.

se wants to know the sum of the preference values over all lines, modulo $10^9+7$. Please tell se the answer.

Input Format

One line with one integer $n$.

Output Format

Output one integer, representing the sum of preference values modulo $10^9+7$.

2

6

1919810

107114211

Hint

Sample Explanation #1

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

Constraints

This problem uses bundled testdata.

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

Translated by ChatGPT 5