You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

黑猫老师在讲台上出了一道看似简单但暗藏玄机的题目：“大橘同学，如果我给你 n 个数字 $a_1, a_2, \cdots, a_n$，你能不能算出这些数字两两相加后的平方和？”

大橘同学揉了揉脑袋，想了想，黑猫老师补充道：“也就是说，你要计算的是：

$\sum_{1 \le i < j \le n} (a_i + a_j)^2$这个值可能会非常大，所以请你只输出它模 1, ⁣000, ⁣000, ⁣007 的结果就行了！”

于是，大橘同学开始奋笔疾算……

输入格式

• 第一行：一个整数 n
• 第二行：n 个整数 $a_1, a_2, \cdots, a_n$

输出格式

• 一个整数：表示结果模 1, ⁣000, ⁣000, ⁣007 的余数。

3
1 2 3

50

数据范围

• 30% 的数据，$1 \le n \le 100， 0 \le a_i < 100$
• 60% 的数据，$1 \le n \le 10000， 0 \le a_i < 10000$
• 100% 的数据，$1 \le n \le 1,\!000,\!000， 0 \le a_i < 1,\!000,\!000$

说明：

$(1+2)^2 + (1+3)^2 + (2+3)^2 = 3^2 + 4^2 + 5^2 = 9 + 16 + 25 = 50$