题目描述

现有一个长度为 $n$ 的数组 $A$.

定义二元函数 $f(x, y) = \sum_{i = x}^y A_i$.

求 $S = \sum_{i = 1}^n \sum_{j = i}^n f(i, j)$.

输入格式

输入包含多组数据。

第一行一个整数 $T$, 代表数据组数。

接下来每组数据包含 $2$ 行。 每组数据中：

第 $1$ 行一个整数 $n$.

第 $2$ 行包含 $n$ 个整数， 第 $i$ 个代表 $A_i$ 的值。

输出格式

对于每组数据， 输出 $S$ $mod$ $1 000 000 007$ 的值。

样例

Sample Input

5
3
1 2 3
9
3 14 15 92 65 35 89 79 32
13
2 7 1 8 2 8 1 8 2 8 4 5 9
2
987654 123456
6
20 20 6 7 18 13

Sample Output

24
8660
2233
2222220
734

Sample Explainion

In the first sample, the result S is 1 + 2 + 3 + (1 + 2) + (2 + 3) + (1 + 2 + 3) = 24.

数据范围与提示

$1 \leq T \leq 5, 1 \leq n \leq 2 \cdot 10^5, 1 \leq A_i \leq 10^6$