给定 $n$ 个整数 $a_1, a_2, \dots, a_n$，Bobo 知道如何计算三元组之和 $$S_3 = \sum_{1 \leq i < j < k \leq n} a_i a_j a_k$$

由此可得 $$S_3 = \frac{(\sum_{1 \leq i \leq n} a_i)^3 - 3 (\sum_{1 \leq i \leq n} a_i^2)(\sum_{1 \leq i \leq n} a_i) + 2(\sum_{1 \leq i \leq n} a_i^3)}{6}$$

Bobo 想要计算四元组之和 $$\left(\sum_{1 \leq i < j < k < l \leq n} a_i a_j a_k a_l\right)\bmod (10^9+7)$$

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

• $1 \leq n \leq 10^5$
• $0 \leq a_i \leq 10^9$
• 测试用例数量不超过 $10$。

输出格式

对于每个测试用例，输出一个整数，表示计算结果。

样例

样例输入 1

3
1 2 3
4
1 2 3 4
5
1 2 3 4 5

样例输出 1

0
24
274