//Code by __dest__ruct__or__(uid=592238)
#include <iostream>
using namespace std;
#define umap unordered_map
#define ll long long
namespace mySTL{
	inline int max(int a,int b){return a>b?a:b;}
	inline int min(int a,int b){return a<b?a:b;}
	inline int abs(int a){return a<0?-a:a;}
	inline int read(){char c=getchar();int f=1,ans=0;
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9')ans*=10,ans+=c-'0',c=getchar();
	return ans*f;}
	inline long long readll(){char c=getchar();long long f=1,ans=0;
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9')ans*=10,ans+=c-'0',c=getchar();
	return ans*f;}
	inline void swap(int &a,int &b){a^=b,b^=a,a^=b;}
	inline void write(int x){if(x<0){putchar('-');x=-x;}
	if(x>=10){write(x/10);}putchar(x%10+'0');}
	inline void writell(long long x){if(x<0){putchar('-');x=-x;}
	if(x>=10){writell(x/10);}putchar(x%10+'0');}
}
using namespace mySTL;
const int mod=1000000007;
int n;
long long a[1000001],q1[1000001],q2[1000001],ans;
int main(void){
	//freopen("data.txt","r",stdin);
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=readll();
		q1[i]=q1[i-1]+a[i];
	}
	for(int i=2;i<=n;i++){
		q2[i]=q2[i-1]+a[i]*(q1[n]-q1[i])%mod;
	}
	for(int i=1;i<=n;i++){
		ans=(ans+a[i]*(q2[n]-q2[i])%mod)%mod;
	}
	writell(6ll*ans%mod);
	return 0;
}

我的方法：
$\sum\limits^N_{i=1}\sum\limits^N_{j=i+1}\sum\limits^N_{k=j+1}a_i\times a_j\times a_k$ 利用分配率可得 $\sum\limits^N_{i=1}(a_i\times \sum\limits^N_{j=i+1}(a_j\times \sum\limits^N_{k=j+1}a_k))$
对整个数列做一次前缀和，优化掉 $\sum\limits^N_{k=j+1}$ 这一层。
对于 $\sum\limits^N_{j=i+1}$ 用 $O(N)$ 的方法再做一次前缀和，优化掉这一层。
之后 $O(N)$ 时间计算 $\sum\limits^N_{i=1}$ 这一层，最后乘上 $6$，输出。
但是全 WA，求调