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

题目内容

在遥远的神秘大陆上，有一座传说中的 元素祭坛。祭坛每次激活时，需要选取一定数量的符文石，并按照某种特定规则排列，只有满足规则的排列才能唤醒祭坛的力量。

现在，祭坛的守护者希望你帮助计算，给定一组符文石，究竟有多少种排列方式能够成功激活祭坛。

祭坛激活规则如下：

1. 符文子序列：通过从原有的符文序列中移除任意数量的符文（可以为 0 个），并保持剩余符文顺序不变所得到的符文序列。
2. $k$ 等级排列：一个长度为 $k$ 的符文序列，序列中的每个符文必须恰好为 $[1, k]$ 的整数值范围，且这些整数恰好各出现一次。例如：
   • $[1, 3, 2, 4]$ 是一个 $4$ 等级排列。
   • $[1, 2, 1, 3]$ 不是一个 $3$ 等级排列，因为数字 $1$ 在序列中重复了两次，不满足每个整数恰好出现一次的条件。

你的任务是计算，给定一组符文石，存在多少种符文子序列可以成为某个 $k$ 等级排列，其中 $k \in [1, n]$。

输入描述

第一行输入一个整数 $n \ (1 \leq n \leq 10^5)$，表示符文石序列的长度。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq 10^9)$，表示每块符文石上刻印的数字。

输出描述

输出一个整数，表示符合祭坛激活规则的符文子序列总数。由于结果可能非常大，请对 $10^9+7$ 取模。

示例

5
1 2 1 3 4

8

说明

符合祭坛规则的符文子序列如下：

1. 等级 $1$：$[1], [1]$ （共 2 种）
2. 等级 $2$：$[1, 2], [2, 1]$ （共 2 种）
3. 等级 $3$：$[1, 2, 3], [2, 1, 3]$ （共 2 种）
4. 等级 $4$：$[1, 2, 3, 4], [2, 1, 3, 4]$ （共 2 种）

总计 $2 + 2 + 2 + 2 = 8$。