该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

C1-粉丝见面会（fans）

题目背景

Lsxszc成为了全宇宙最强OIer！许多粉丝慕名而来拜访！

现在Lsxszc决定搞一个小活动，活动要求五个生物参加，存在特殊要求，需要你帮忙告诉他选五个生物的方案有多少个。

题目描述

现场有 $n$ 位粉丝，第 $i$ 个粉丝物种是 $a_i$，活动要求选择五个位置不同的生物，其中前三个位置的物种相同，后两个位置的物种彼此不同且都不同于前三个位置的物种。

换而言之，给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，请计算满足以下条件的下标五元组 $(i, j, k, p, q)$ 的数量：

• $1 \leq i, j, k, p, q \leq n$
• $i, j, k, p, q$ 互不相同（五个下标两两不同）
• $a_i = a_j = a_k$
• $a_p \neq a_i$
• $a_q \neq a_i$
• $a_p \neq a_q$

即要从序列中选出五个不同的位置，其中三个位置的数值相同，另外两个位置的数值彼此不同且都不同于前面那个数值。

我们关注的是选择五个不同的位置，而不是它们的顺序。即：

• 选择三个相同值的位置集合 $\{i,j,k\}$（无序）
• 选择另外两个不同值的位置 $p,q$（有序，因为 $p$ 和 $q$ 对应不同的值）

输入格式

$n$

$a_1 \ \ a_2 \ \ \dots \ \ a_n$

输出格式

输出一个整数，表示满足条件的方案数量。

由于答案可能很大，你只需要输出答案 $\mod 10^9+7$ 即可。

输入输出样例 #1

输入 #1

5
1 1 1 2 3

输出 #1

2

输入输出样例 #2

输入 #2

6
1 1 1 2 2 3

输出 #2

4

说明/提示

样例解释 1

可行的方案：

• 选择三个 1（位置 1,2,3），再选择 2（位置 4）和 3（位置 5）
• 选择三个 1（位置 1,2,3），再选择 3（位置 5）和 2（位置 4）

样例解释 2

可行的方案：

• 选择位置 4（值2）和 6（值3）：(1,2,3,4,6)
• 选择位置 5（值2）和 6（值3）：(1,2,3,5,6)
• 选择位置 6（值3）和 4（值2）：(1,2,3,6,4)
• 选择位置 6（值3）和 5（值2）：(1,2,3,6,5)

数据范围：

对于所有测试点：

• $1 \leq n \leq 10^5$
• $1 \leq a_i \leq 10^9$

后记

Lsxszc最终集结到了3只草履虫，1头北极熊，1条鲸鱼。