Problem #3618 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

求在 $n \times n$ 矩形内（包括边界）整点三角形有多少个。由于答案可能很大，对于 $10^{9} + 7$ 取模。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^{6})$ 表示矩形的宽与高。

输出格式

一个整数 $x$ 。

样例

Input

Output

Input

Output

提示

做不出来可以试试打表找规律？

6 人解决，54 人已尝试。

10 份提交通过，共有 397 份提交。

9.0 EMB 奖励。

创建: 6 年，9 月前.

修改: 6 年，7 月前.

最后提交: 5 月前.

来源: N/A

math number theory