时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的正整数数组 $a$。

对于数组中的任意一对不同位置 $i, j$，其中 $i < j$，定义这一对数的“有趣值”为：

$$|a_i - a_j| \times (a_i + a_j)$$

也就是说，这一对数的“有趣值”等于它们差的绝对值$^\dagger$乘以它们的和。

请你计算数组中所有不同数对的“有趣值”的和。即：

$$\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} |a_i - a_j| (a_i + a_j) $$

由于答案可能很大，你只需输出答案对 $10^9 + 7$ 取模后的结果。

绝对值$^\dagger$: $|x|$ 表示整数 $x$ 的绝对值，定义为：

$$|x| = \begin{cases} x, & x \ge 0 \\ -x, & x < 0 \end{cases} $$

例如，$|3-1|=2$，$|1-3|=2$。

格式

输入格式

第一行包含一个整数 $n$，表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，中间用空格隔开。

输出格式

输出一个整数，表示“有趣值”的和对 $10^9 + 7$ 取模后的结果。

样例

样例输入 #1

3
3 1 2

样例输出 #1

16

样例解释 #1

• 当 $i=1, j=2$ 时：$|a_1 - a_2|(a_1 + a_2) = |3 - 1| \times (3 + 1) = 2 \times 4 = 8$
• 当 $i=1, j=3$ 时：$|a_1 - a_3|(a_1 + a_3) = |3 - 2| \times (3 + 2) = 1 \times 5 = 5$
• 当 $i=2, j=3$ 时：$|a_2 - a_3|(a_2 + a_3) = |1 - 2| \times (1 + 2) = 1 \times 3 = 3$

总和为 $8 + 5 + 3 = 16$。$16 \bmod{(10^9 + 7)} = 16$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$40$	$3000$
$2$	$60$	$10^6$

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le a_i \le 10^9$。