Description

For $A_1, A_2, A_3, \cdots, A_N$, compute

$$(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)$$

Input Format

Line 1: one integer $N$.

Line 2: $N$ integers $A_1, A_2, A_3, \cdots, A_N$.

Output Format

One integer, representing the required value.

3
1 2 3

36

Hint

• For 30% of the testdata, $N \le 500$.
• For 60% of the testdata, $N \le 5000$.
• For 100% of the testdata, $3 \le N \le 10^6$, $0 \le A_i \le 10^9$.

Translated by ChatGPT 5