Triple Product Sum Modulo

Given an array \(A_1, A_2, \ldots, A_N\), compute the following expression:

\[ (6 \times \sum_{i=1}^{N}\sum_{j=i+1}^{N}\sum_{k=j+1}^{N} A_i \times A_j \times A_k) \bmod (10^9+7) \]

You may use the identity below to simplify the computation:

\[ \sum_{i<j<k} A_i A_j A_k = \frac{(\sum_{i=1}^{N}A_i)^3 - 3(\sum_{i=1}^{N}A_i)(\sum_{i=1}^{N}A_i^2) + 2(\sum_{i=1}^{N}A_i^3)}{6} \]

Multiplying both sides by 6 gives:

\[ 6\times \sum_{i<j<k} A_i A_j A_k = (\sum_{i=1}^{N}A_i)^3 - 3(\sum_{i=1}^{N}A_i)(\sum_{i=1}^{N}A_i^2) + 2(\sum_{i=1}^{N}A_i^3) \]

Output the result modulo \(10^9+7\).

inputFormat

The first line contains an integer \(N\) -- the number of elements in the array. The second line contains \(N\) space-separated integers representing the array \(A_1, A_2, \ldots, A_N\).

outputFormat

Output a single integer which is the computed result of the expression modulo \(10^9+7\).

sample

3
1 2 3

36