题目描述

给定一个长为\(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\)。