思路：公式变换

对于每个元素，考虑其贡献 假设下标从 00 开始 第$i$ 个元素为第1个的子数组数量为：$n-i$个 第 $i$ 个元素为第2个的子数组的数量为$n-(i-1)-1=n-i$个

第 $i$ 个元素为第3个的子数组的数量为$n-(i-2)-2=n-i$个

第 $i$个元素为第$j$个的子数组的数量为$n-(i-(j-1))-(j-1)=n-i$ 个

题目描述

小红有一个长度为 $n$ 的数组 $a$ ，下标从 $1$ 开始。

他对这个数组的权值定义为：$1\times a_1+2\times a_2 + 3\times a_3 + \cdots + n\times a_n$

现在小红想要问你，这个数组的所有连续子数组的权值之和是多少。

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$，表示数组的长度。
第二行，$n$ 个整数，第 $i$ 个整数为 $a_i(1 \leq a_i \leq 10^9)$ 。

输出描述

一个非负整数，表示所有子数组的权值之和，答案对 $10^9+7$ 取模

样例

输入

3
1 2 3

输出

33

说明 对于子数组 $a[1]$ 来说，权值为 $1$
对于子数组 $a[2]$ 来说，权值为 $2$
对于子数组 $a[3]$ 来说，权值为 $3$
对于子数组 $a[1,2]$ 来说，权值为 $5$
对于子数组 $a[2,3]$ 来说，权值为 $8$
对于子数组 $a[1,2,3]$ 来说，权值为 $14$
总和为 $33$ 。