1433 - 数正方形
描述

在一个 N \times N 的点阵上,取其中 4 个点恰好组成一个正方形的 4 个顶点,一共有多少种不同的取法?

由于结果可能非常大,你只需要输出模 10^9 + 7 的余数。

2022_09_30_4ab10c5eb27e3dea37d8g-09.jpg

如上图所示的正方形都是合法的。


输入

输入包含一个整数 N

输出

输出一个整数代表答案。

样例

输入

4

输出

20
提示

对于所有评测用例,2 ≤ N ≤ 10^6

蓝桥杯 2019 年国赛 C 组 G 题


题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 51
通过次数 17