题目描述

小蓝正在二维坐标系中构造正方形，他手上有 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，他想知道有多少个有序四元组 $(i, j, p, q)$ 满足 $i, j, p, q$ 互不相同，且四个点：$(0,0)$、$(-a_i, a_j)$、$(a_p, a_q)$、$(a_p - a_i, a_j + a_q)$ 能构成一个正方形？

输入格式

输入的第一行包含一个正整数 $n$ 。

第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$ ，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。答案可能很大，请输出答案除以 $1000000007$ （即 $10^9 + 7$ ）的余数。

15
1 1 1 1 2 2 1 2 2 2 1 1 1 1 1

8760

提示

【样例说明】

可用的数一共有 $10$ 个 $1$ 和 $5$ 个 $2$。

取 $a_i = 1, a_j = 2, a_p = 2, a_q = 1$ 时，有 $A_{10}^2 A_{5}^2 = 1800$ 种方案；

取 $a_i = 2, a_j = 1, a_p = 1, a_q = 2$ 时，有 $A_{10}^2 A_{5}^2 = 1800$ 种方案；

取 $a_i = 1, a_j = 1, a_p = 1, a_q = 1$ 时，有 $A_{10}^{4} = 5040$ 种方案；

取 $a_i = 2, a_j = 2, a_p = 2, a_q = 2$ 时，有 $A_{5}^{4} = 120$ 种方案；

总共有 $8760$ 种方案。

【评测用例规模与约定】

对于 $40\%$ 的评测用例，$1 \leq n \leq 100$；

对于所有评测用例，$1 \leq n \leq 1000000$，$1 \leq a_i \leq 1000$。