[YDOI R1] Lattice

jjh 喜欢点阵。

jjh 有一个正方形点阵，这个点阵以 $(1,1)$ 为左下角，以 $(n,n)$ 为右上角。 jjh 还有一条直线，其表达式为 $y=kx$，其中 $k\in(0,\infty)$。 对于任意一个 $k$，设该直线经过了 $cnt$ 个点阵中的点，jjh 对这条直线有一个喜爱程度，为 $cnt^2$。 jjh 想知道所有直线的喜爱程度和对 $10^9+7$ 取模的结果，请你告诉 jjh。

一行一个整数 $n$。

输出一个整数，表示喜爱程度和对 $10^9+7$ 取模的结果。

2

6

1919810

107114211

### 样例解释 #1 当 $k$ 为 $\frac{1}{2}$ 时，直线过点阵中的点 $(2,1)$，喜爱程度为 $1^2=1$；当 $k$ 为 $1$ 时，直线过点阵中的点 $(1,1)$ 和点 $(2,2)$，喜爱程度为 $2^2=4$；当 $k$ 为 $2$ 时，直线过点阵中的点 $(1,2)$，喜爱程度为 $1^2=1$。喜爱程度和为 $1+4+1=6$。 ### 数据范围 **本题采用捆绑测试**。 |子任务编号|$n\le$|分值| |:--:|:--:|:--:| |$1$|$8$|$5$| |$2$|$10^3$|$15$| |$3$|$10^6$|$30$| |$4$|$2^{31}-1$|$50$| 对于 $100\%$ 的数据，$1\le n\le 2^{31}-1$。