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.

Description

给定 $n$ 个整数 $a_1, a_2, \dots, a_n$​ ，请求出两两数字和的平方的和，也就是

由于这个数字比较大，输出答案模 $10^9 + 7$ 的余数。

Format

Input

第一行单个整数 $n$

第二行$n$个整数 $a_1, a_2, \dots, a_n$​

Output

一行一个整数表示答案

Samples

样例输入

3
1 2 3

样例输出

50

样例解释

$(1 + 2)^2 + (1 + 3)^2 + (2 + 3)^2$

Limitation

• 30%: $1 \leq n \leq 100$, $0 \leq a_i \leq 100$
• 60%: $1 \leq n \leq 10^4$, $0 \leq a_i \leq 10^4$
• 100%: $1 \leq n \leq 2 \times 10^5$, $0 \leq a_i \leq 2 \times 10^5$

1s, 512MiB for each test case.