#P4798. [CEOI2015 Day1] 卡尔文球锦标赛

[CEOI2015 Day1] 卡尔文球锦标赛

题目描述

译自 CEOI2015 Day1 T2「Calvinball championship

一场卡尔文球比赛会有 nn 名选手参与,他们的编号分别为 1n1\dots n,分为若干个非空的球队。我们规定球队之间按照每个球队编号最小的选手的编号排序,并且以从 1 开始的连续整数编号。

举个栗子,譬如 1 号选手自己成一队,2, 3 和 5 号选手成一队,4 和 6 号选手成一队。

>  1\ \texttt{1}
>  2 3 5\ \texttt{2 3 5}
>  4 6\ \texttt{4 6}

那么 1 号选手的球队就是 1 号球队,2 号选手的球队就是 2 号球队,4 号选手的球队就是 3 号球队。

>  1|1\ \texttt{1|1}
>  2|2 3 5\ \texttt{2|2 3 5}
>  3|4 6\ \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 0071\ 000\ 007 取余的结果。

输入格式

第一行,一个正整数 n(1n10 000)n(1 \leq n \leq 10\ 000)

第二行,nn 个以空格分隔的正整数,表示任务所给的球队记录。

输出格式

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

3
1 2 2
4

提示

请注意,三人比赛中可能的选择有 1 1 1 1 1 2 1 2 1 1 2 21 2 3

数据范围与提示

数据点 131-3 454-5 676-7 8108-10
nn\le 1414 100100 1 0001\ 000 10 00010\ 000