Given $n$ integers $a_1, a_2, \dots, a_n$, Bobo knows how to compute the sum of triples $$S_3 = \sum_{1 \leq i < j < k \leq n} a_i a_j a_k.$$
It follows that $$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 would like to compute the sum of quadrangles $$\left(\sum_{1 \leq i < j < k < l \leq n} a_i a_j a_k a_l\right)\bmod (10^9+7).$$
Input
The input contains zero or more test cases and is terminated by end-of-file. For each test case,
The first line contains an integer $n$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$.
- $1 \leq n \leq 10^5$
- $0 \leq a_i \leq 10^9$
- The number of tests cases does not exceed $10$.
Output
For each case, output an integer which denotes the result.
Sample Input
3 1 2 3 4 1 2 3 4 5 1 2 3 4 5
Sample Output
0 24 274