题目描述

在 Sashkalandia 王国中，有 $N$ 位公民，编号为 $1$ 到 $N$，每个人都可以参加投票。

这个国家里有若干个政党，政党的编号也用 $1$ 到 $N$ 之间的整数表示。第 $i$ 位公民只会把票投给编号为 $P_i$ 的政党。

Sashka 是这个国家里极具影响力的人物，因此每位公民都会向她咨询：

• 是去给自己支持的政党投票，还是
• 干脆不参加选举。

并且每位公民都会完全听从她的建议。

于是，Sashka 想知道：她有多少种不同的咨询方式，使得得票最多的政党获得了全民投票中的多数？

形式化地说：

给定序列 $P_1, P_2, \dots, P_N$，问它有多少个非空子序列拥有一个主元素（majorant）。

由于答案可能很大，你只需要输出它对 $10^9+7$ 取模后的结果。

请编写程序 elections 来计算这个值。

说明

因为 $10^9+7$ 是质数，根据费马小定理，对于任意不被 $10^9+7$ 整除的整数 $x$，都有：

$$x^{10^9+6} \equiv 1 \pmod{10^9+7}$$

因此，$x$ 在模 $10^9+7$ 意义下存在逆元 $x^{-1}$，并且：

$$x^{-1} \equiv x^{10^9+5} \pmod{10^9+7}$$

也就是说，本题中可以在模意义下进行“除法”。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $P_1, P_2, \dots, P_N$。

输出格式

输出一个整数，表示满足条件的非空子序列个数，对 $10^9+7$ 取模。

数据范围

• $1 \le N \le 2 \times 10^6$
• $1 \le P_i \le N$

名词解释

• 非空子序列：从原序列中删去若干元素（也可以一个都不删），并保持剩余元素的相对顺序后得到的非空序列。
• 主元素（majorant）：在一个序列中，出现次数严格大于该序列长度一半的元素。

子任务

子任务	分值	依赖子任务	$N$ 范围	其它限制
0		-		样例
1	10	0	$\le 20$	无
2	15	-	$\le 10^5$	$P_i \le 2$
3				每个政党最多有两个支持者
4	25	0-1	$\le 10^3$	无
5		0-4	$\le 10^6$
6	10	0-5	$\le 2 \times 10^6$

只有通过某个子任务以及其所有依赖子任务的全部测试点，才能获得该子任务的分数。

样例 1

输入

3
2 1 2

输出

5

样例解释

满足条件的子序列对应于选择以下编号的公民参加投票：

• $\{1\}$
• $\{2\}$
• $\{3\}$
• $\{1,3\}$
• $\{1,2,3\}$

一共 5 种。

样例 2

输入

8
1 3 4 3 3 2 3 1

输出

104

样例解释

例如，若选择编号为 $\{1,2,3,4,5,6,7\}$ 的公民参加投票，则 3 号党将获得 4 票，而：

$$\frac{7}{2} = 3.5$$

所以 3 号党是主元素。

而若所有公民都参加投票，则不存在主元素，因为任何政党的得票数都不会超过 $\frac{8}{2}=4$。