题目描述

对于$A_1,A_2,A_3,\cdots,A_N$，求

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

输入格式

第一行，一个整数 $N$。

第二行，$N$ 个整数 $A_1,A_2,A_3,\cdots,A_N$。

输出格式

一个整数，表示所求的值。

3
1 2 3

36

提示

• 对于 $30\%$ 的数据，$N \le 500$；
• 对于 $60\%$ 的数据，$N \le 5000$；
• 对于 $100\%$ 的数据，$3 \le N \le 10^6$，$0 \le A_i \le 10^9$。