Question
Pair Product Sum Calculation
Emma has a list of N integers, A1, A2, ..., An, and she wants to compute the “pair product sum” of the list. This sum is calculated by taking the product of each unique pair (i, j) where 1 ≤ i < j ≤ N and adding them all together. Specifically, for each pair, she calculates Ai * Aj, then finds the total sum of these products. Return the result modulo 109 + 7.
Input
The first line of the input contains a single integer N, denoting the size of an array.
The next line of the input contains N space-separated integers A1, A2,. . An.
Constraints
2 ≤ N ≤ 2 x 105
0 ≤ Ai ≤ 109
The next line of the input contains N space-separated integers A1, A2,. . An.
Constraints
2 ≤ N ≤ 2 x 105
0 ≤ Ai ≤ 109
Output
Print the answer.
Example
Sample Input
4
1 2 3 4
Sample Output
35
Explanation
1 x 2 + 1 x 3 + 1 x 4 + 2 x 3 + 2 x 4 + 3 x 4 = 35
4
1 2 3 4
Sample Output
35
Explanation
1 x 2 + 1 x 3 + 1 x 4 + 2 x 3 + 2 x 4 + 3 x 4 = 35