Nice Trick

用四组数据1，2，3，4； 2，3，4，5；1，3，4，5； 1，2，4，5；来待定系数法推出四元时的公式。。。

#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
const int mod = 1e9 + 7;
const int inv = 41666667;
int main() {
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n) {
        long long sum[4], a, temp;
        for(int i=0;i<4;i++)sum[i]=0;
        for (int i = 0; i < n; i++) {
            cin >> a; temp = a;
            for (int j = 0; j < 4; j++) {
                sum[j] = (sum[j] + temp) % mod;
                temp = temp * a%mod;
            }
        }
         if(n<4){
            cout<<0<<endl;
            continue;
        }
        long long ans = (sum[0] * sum[0] % mod*sum[0] % mod*sum[0]) % mod;
        ans = (ans + 8 * sum[0] % mod*sum[2] % mod) % mod;
        ans = (ans + 3 * sum[1] % mod*sum[1]) % mod;
        ans = (ans + mod - 6 * sum[0] % mod*sum[0] % mod*sum[1] % mod) % mod;
        ans = (ans + mod - 6 * sum[3] % mod) % mod;
        ans = (ans*inv) % mod;
        cout << ans << endl;
    }
    return 0;
}