题目背景

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$。