题目描述

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

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

text 1 2 3 5 4 6 那么 $1$ 号选手的球队就是 $1$ 号球队，$2$ 号选手的球队就是 $2$ 号球队，$4$ 号选手的球队就是 $3$ 号球队。

1|1

2|2 3 5

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$