来源：牛客网
@[toc]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

定义S(n) = 12 + 22 + … + n2，输出S(n) % 1000000007。

注意：1 < n < 1e18。

输入描述:

多组输入，输入直到遇到EOF为止；

第一行输入一个正整数n。

输出描述:

输出S(n) % 1000000007的结果。

示例1
输入

1
2
1000

输出

1
5
333833500

题解：

平方和公式：1^2^+2^2^+3^2^+......+n^2^=n(n+1)(2n+1)/6
（建议补一补高中的一些公式，我也没想起来 ）
注意题目是要mod的
模运算：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^b^ % p = ((a % p)^b^) % p
我们可以发现唯独没有除法的模运算，但是公式中有个 /6 需要处理，那我们可以用逆元的方式将除法变成乘法
逆元：整数a,b，满足a * b = 1（mod m），那么称b是a的模m乘法逆元
比如：A/B%C我们可以写成A * （1 / B）% C，这样就是AX%C的形式，如何求X？和上面的逆元结合起来就OK了
这样/6%mod，我就可以写成 inv（6）%mod
求逆元的方法这里就不详细介绍了

代码：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;  //到达递归边界开始向上一层返回
    }
    ll gcd=exgcd(b,a%b,x,y);
    ll y1=y;    //把x y变成上一层的
    ll x1=x;
    y=x1-(a/b)*y1;
    x=y1;
    return gcd;     //得到a b的最大公因数
}
ll inv(ll a,ll mod){
    ll x,y;
    ll gcd=exgcd(a,mod,x,y);
    if(gcd!=1)return -1;
    else return (x+mod)%mod; 
}
int main()
{
    ll n;
    while(cin>>n){
        ll ans=0;
        ans=(((n%mod)*((n+1)%mod)%mod*((2*n+1)%mod))%mod);
        ll inv6=inv(6,mod);
        ans=(ans%mod*inv6%mod)%mod;
        cout<<ans<<endl;
    }
    return 0;
}