题目描述

输入一个长度为n的数组$a$，$a$包括$\frac{(n+1)*n}{2}$个区间。每个区间所有数的和，被称为区间和，求所有$\frac{ (n+1)*n }{2}$个区间和的和。由于数值较大，输出mod 1e9+7的结果。

例如：

3个数1 2 3，共有6个子区间，包含的数字如下：{1} {2} {3} {1 2} {2 3} {1 2 3}，这些区间求和为1 2 3 3 5 6，这6个数字再求和为20.

输入格式

第一行一个整数n，表示数组长度接下来n行，每行一个整数ai，表示数组的内容。$(0<=ai<=50000)$

输出格式

输出答案mod 1e9+7

样例

输入

3
1
2
3

输出

20

提示

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

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

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