利用好S3的公式，枚举第4项，每次都计算S3公式中所需要的三个和，然后当i>3时每次输入a[i]时都算一遍S3，并计算a[i]*S3的值，最后加起来即可。
边加边模，防止溢出。
知识点：
快速幂取模
费马小定理

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e5+5;
const ll inv=166666668;//6对mod的逆元
ll POW(ll x,ll y)//快速幂取模
{
    ll res=1;
    while(y)
    {
        if(y&1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return res%mod;
}
ll solve(ll x,ll y,ll z)//计算此时S3的值
{
    ll res=0;
    res=(res+POW(x,3))%mod;
    res=((res-(3*y*x%mod))%mod+mod)%mod;//防止出现负数
    res=(res+2*z)%mod;
    res=res*inv%mod;//除6
    return res;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        ll sum1=0,sum2=0,sum3=0;//S3公式中所需要的三个和
        ll ans=0;
        int a;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            if(i>3)
                ans=(ans+a*solve(sum1,sum2,sum3))%mod;//代入S3的公式
            sum1=(sum1+a)%mod;//求三个sum的值
            sum2=(sum2+POW((ll)a,(ll)2))%mod;
            sum3=(sum3+POW((ll)a,(ll)3))%mod;

        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}