题目描述
给定一个长度为 N 的整数序列 C。找出满足以下条件的长度为 N 的整数序列 A 的数量。
- 1≤Ai≤Ci(1≤i≤N)
- Ai=Aj(1≤i<j≤N)
由于可能的数量很大,所以对 (109+7) 取模。
约束条件
- 1≤N≤2×105
- 1≤Ci≤109
- 输入中的所有值都是整数。
输入
输入以以下格式从标准输入中给出:
N
C1 C2 … CN
输出
打印满足以上条件的长度为 N 的整数序列 A 的数量,取模 (109+7)。
示例输入 1
示例输出 1
满足条件的序列 A 有两个:(1,2) 和 (1,3)。
另一方面,像 A=(1,1) 这样的序列不满足第二个条件。
示例输入 2
示例输出 2
示例输入 3
示例输出 3
没有满足条件的序列 A,所以应该打印 0。
示例输入 4
示例输出 4
请务必打印取模 (109+7) 的结果。