Description

输入一个长度为n的数组a, a包括(n+1)n/2个区间。每个区间所有数的和,被称为区间和,求所有(n+1)n/2个区间和的和。由于数值较大,输出mod 1e9+7的结果。例如:3个数123,共有6个子区间,包含的数字如下:[1] [2] [3] [1 2] [2 3] [1 2 3],这些区间求和为1 2 3 3 5 6,这6个数字再求和为20.

Input Format

第一行一个整数n，表示数组长度，接下来n行，每行一个整数，表示数组的内容。

对于30%的数据，1<=n<=100;

对于50%的数据，1<=n<=1000;

对于100%的数据，1<=n<=100000。

每个数不超过int

Output Format

输出答案%1000000007

3
1
2
3

20

Source