题目描述

给定$n$个整数$a_1,a_2,\cdots,a_n$，需要计算所有满足$1\leq i < j \leq n$的$(a_i + a_j)^2$的和，即$\sum_{1\leq i < j \leq n}(a_i + a_j)^2$ 。由于计算结果可能非常大，最终输出答案对$1,000,000,007$取模的余数。

输入格式

• 第一行：一个整数$n$，表示整数的个数。
• 第二行：$n$个整数$a_1,a_2,\cdots,a_n$，以空格分隔。

输出格式

一个整数，为计算得到的和对$1,000,000,007$取模后的余数。

数据范围

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

样例数据

• 输入

3
1 2 3

• 输出

50

• 说明：计算过程为$3\times3 + 4\times4 + 5\times5$ ，其中$3 = 1 + 2$，$4 = 1 + 3$，$5 = 2 + 3$ 。

$\sum_{1\leq i < j \leq n}(a_i + a_j)^2$ 。根据完全平方公式 $(a + b)^2 = a^2 + 2ab + b^2$，可将原式展开为： $\sum_{1\leq i < j \leq n}(a_i^2 + 2a_ia_j + a_j^2)$