题目描述

给定一个长为$n$的序列$a$，求：

$$\left(\sum_{i=1}^{i\leq n}\sum_{j=i}^{j\leq n}\sum_{k=i}^{k\leq j}a_k\right)\bmod10^9+7$$

输入格式

输入$n$和序列$a$。

输出格式

输出$\displaystyle\left(\sum_{i=1}^{i\leq n}\sum_{j=i}^{j\leq n}\sum_{k=i}^{k\leq j}a_k\right)\bmod10^9+7$。

输入样例

3
1 2 3

输出样例

20

样例解释

• 当$i=1$时：
  • 当$j=1$时，$\displaystyle\sum_{k=i}^{k\leq j}a_k=1$
  • 当$j=2$时，$\displaystyle\sum_{k=i}^{k\leq j}a_k=3$
  • 当$j=3$时，$\displaystyle\sum_{k=i}^{k\leq j}a_k=6$
• 当$i=2$时：
  • 当$j=2$时，$\displaystyle\sum_{k=i}^{k\leq j}a_k=2$
  • 当$j=3$时，$\displaystyle\sum_{k=i}^{k\leq j}a_k=5$
• 当$i=3$时：
  • 当$j=3$时，$\displaystyle\sum_{k=i}^{k\leq j}a_k=3$

综上所述，$1+3+6+2+5+3=20$。

数据范围

本题共$20$个测试点，$2$个满足$n\leq100$，$6$个满足$n\leq10^4$，全部满足$n\leq10^5$，且对于$1\leq i\leq n$，$|a_i|\leq10^9$。