【题目描述】

牛顿的实验台上摆着 $n$ 支音叉，第 $i$ 支音叉的振动频率为 $a_i$．任意两支音叉同时振动时，频率相差越大，实验装置记录到的差异能量就越高．

实验装置会让每一对不同的音叉恰好同时振动一次．对于编号满足 $1\le i<j\le n$ 的一对音叉，装置记录的差异能量定义为 $|a_i-a_j|^2$．

请计算全部实验产生的差异能量之和，也就是

$$\sum_{1\le i<j\le n}|a_i-a_j|^2$$

对 $10^9+7$ 取模后的结果．

输入格式

第一行输入一个整数 $n$，表示音叉数量．

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 支音叉的振动频率．

输出格式

输出一个整数，表示所有差异能量之和对 $10^9+7$ 取模后的值．

样例 1

输入

4
1 2 4 7

输出

84

解释

六对音叉产生的差异能量依次为

$$1,9,36,4,25,9,$$

它们的总和为 $84$．

样例 2

输入

2
0 1000000000

输出

49

解释

两支音叉产生的差异能量为 $10^{18}$，它对 $10^9+7$ 取模后的结果为 $49$．

样例 3

见选手目录下的 Data/sample3.in 和 Data/sample3.ans．

该样例对应子任务 $1$，满足 $n\le200$．

样例 4

见选手目录下的 Data/sample4.in 和 Data/sample4.ans．

该样例对应子任务 $2$，满足 $n\le5000$．

样例 5

见选手目录下的 Data/sample5.in 和 Data/sample5.ans．

该样例对应子任务 $3$，满足 $a_i\in\{0,1\}$．

样例 6

见选手目录下的 Data/sample6.in 和 Data/sample6.ans．

该样例对应子任务 $4$，满足 $0\le a_i\le1000$．

样例 7

见选手目录下的 Data/sample7.in 和 Data/sample7.ans．

该样例对应子任务 $5$，无特殊性质．

数据范围与约定

对于所有测试数据，保证：

• $1\le n\le10^6$；
• $0\le a_i\le10^9$．

子任务编号	分数	特殊性质
$1$	$10$	$n\le200$
$2$	$20$	$n\le5000$
$3$	$15$	$a_i\in\{0,1\}$
$4$		$0\le a_i\le1000$
$5$	$40$	无特殊性质

【大样例下载链接】

点击下载本题选手目录