题目描述

塔子哥有一个长度为 $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$ 。