Problem Description

街道上依次坐落着n个景点，每个景点都有一个美丽度a[i]。

定义[l,r]之间景点的美丽度为(r-l+1)*a[l]+(r-l)*a[l+1]+...+2*a[r-1]+1*a[r]

现在我们想要知道对于所有的子区间，景点的美丽度和为多少。

Input

第一行输入一个整数n(1<n<=1000000)，

第二行输入n个整数。

0<=ai<=1e9

Output

输出所有区间的美丽度和(由于输出结果太大，答案取模1e9+7)。

Sample Input

3

1 2 3

5

1 2 3 4 5

Sample Output

27

182

思路：

a[i]的贡献很容易算得是a[i] * (n-i) * sum[n-i+1] ，其中sum数组表示数列1,2,3,4....的前缀和。

代码：

#include
      
        using namespace std;#define LL long long#define INF 2000000000LL ans[1000001];const LL mod = 1e9+7;void init(){    ans[0] = 0;    for(int i = 1 ; i <= 1000000 ; i++){        ans[i] = (ans[i-1] + i + 0LL)%mod;    }}//求前缀和 int main(){    int n;    init();    while(~scanf("%d",&n)){        int k = n;        LL sum = 0;        for(int i = 1 ; i <= n ; i++){            LL x;scanf("%lld",&x);            LL cnt = (((x*i)%mod*ans[n-i+1])%mod)%mod;            sum = (sum+cnt)%mod;        }        printf("%lld\n",(sum+mod)%mod);    }}/*31 2 351 2 3 4 5*/