题目描述

输入一个长度为 n 的数组 a ，a 包括 (n+1)*n/2 个区间。每个区间所有数的和，被称为区间和。

求所有 (n+1)*n/2 个区间和的和。由于数值较大，输出模 $10^9+7$ 的结果。 例如: 3 个数 1 2 3 ，共有 6 个子区间，包含的数如下:

{1} , {2} , {3} , {1 2} , {2 3} , {1 2 3}，这些区间求和为 1 2 3 3 5 6 ，这 6 个数字再求和为 20 。

数据范围

1 <= n <= 100000 ，每个数不超过 int 。

输入格式

第一行一个整数 ，表示数组长度；

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

输出格式

一个整数，代表答案 mod $10^9+7$

样例

3
1
2
3

20