[CEOI2015 Day1] 卡尔文球锦标赛

**译自 [CEOI2015](https://ceoi2015.fi.muni.cz/tasks.php) Day1 T2「[Calvinball championship](https://ceoi2015.fi.muni.cz/day1/eng/day1task2-eng.pdf)」** 一场卡尔文球比赛会有 $n$ 名选手参与，他们的编号分别为 $1\dots n$，分为若干个非空的球队。我们规定球队之间按照每个球队编号最小的选手的编号排序，并且以从 1 开始的连续整数编号。 举个栗子，譬如 1 号选手自己成一队，2, 3 和 5 号选手成一队，4 和 6 号选手成一队。 >\> $\ \texttt{1}$ >\> $\ \texttt{2 3 5}$ >\> $\ \texttt{4 6}$ 那么 1 号选手的球队就是 1 号球队，2 号选手的球队就是 2 号球队，4 号选手的球队就是 3 号球队。 >\> $\ \texttt{1|1}$ >\> $\ \texttt{2|2 3 5}$ >\> $\ \texttt{3|4 6}$ 每个人每天会选择不同的球队，我们可以在记录时省略选手的编号，仅记录每个位置对应选手所属球队编号的序列（上述例子为 `1 2 2 3 2 3`），因为每天的选手是一样的。当可能的选择方案全部被使用过后，锦标赛就结束了。 由于选择方案十分多，选择困难症患者纷纷表示力不从心。今年，我们决定根据记录的序列的字典序来选择方案。因此，第一天，所有人都在一个队 `1 1 1 1 1`；第二天，所有人都与 6 号针锋相对 `1 1 1 1 1 2`……在最后一天，所有人互相打响战争 `1 2 3 4 5 6`。 对于给定的球队记录，请你算出将会在未来的哪一天使用该记录。输出这个数字对 $1\ 000\ 007$ 取余的结果。

第一行，一个正整数 $n(1 \leq n \leq 10\ 000)$。 第二行，$n$ 个以空格分隔的正整数，表示任务所给的球队记录。

输出一个正整数，表示任务所给的球队记录将会被使用的天数对 $1\ 000\ 007$ 取余的结果。第一天的天数为 1。

3
1 2 2

4

请注意，三人比赛中可能的选择有 `1 1 1` `1 1 2` `1 2 1` `1 2 2` 和 `1 2 3`。 ### 数据范围与提示 |数据点|$1-3$|$4-5$|$6-7$|$8-10$| |-|:-:|:-:|:-:|:-:| |$n\le$|$14$|$100$|$1\ 000$|$10\ 000$|