#11639. 妖梦拼木棒

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

妖梦斩了一地的木棒,现在她想要将木棒拼起来。

n 根木棒,现在从中选 4 根,想要组成一个正三角形(等边三角形),问有几种选法?

答案对 10^9+7 取模。

输入格式

第一行一个整数 n

第二行往下 n 行,每行 1 个整数,第 i 个整数 a_i 代表第 i 根木棒的长度。

输出格式

一行一个整数代表答案。

样例

样例输入 #1

4 
1
1
2
2

样例输出 #1

1

解释: 1和1合起来作为一条边,两个2作为另外两条边,可以构成正三角形。

数据范围与提示

  • 对于 20\% 的数据,保证 n \le 100

  • 对于 50\% 的数据,保证 n \le 1000

  • 对于 70\% 的数据,保证 n \le 5 \times 10^3

  • 对于 100\% 的数据,保证 1 \leq n \le 10^5 1 \le a_i \le 5 \times 10^3