题目描述

有 $n$ 个人参加一场比赛，需要把他们分成若干组，然后就会给他们每人一个编号。

编号发放的规则：

1. 每个组的队长为组员中名字字典序最小的那个人；

2. 每个组的编号为这个组的队长名字的排名（按字典序，且只有队长参与排名）；

3. 每个人的编号即为他所在组的编号，然后将所有人按字典序排好，根据他们的编号就可以产生一个序列。

例如： 有 $6$ 个人，分为 $3$ 组 （Calvin，Hobbes，Susie），（Batman），（Jerry ，Tom），加粗的是队长。（Batman）为第一组，（Calvin，Hobbes，Susie）为第二组，（Jerry ，Tom）为第三组。所以 $6$ 人编号分别为 Batman $1$ ，Calvin $2$，Hobbes $2$，Susie $2$，Jerry $3$，Tom $3$。 再将 $6$ 人名字排序，有 Batman $1$ Calvin $2$ Hobbes $2$ Jerry $3$ Susie $2$ Tom $3$ ，所以序列为 $1,2,2,3,2,3$。

现在给出一个序列，求它按照字典序是第多少大的，答案 $\bmod 1000007$。（具体意思见样例解释）

输入格式

第一行一个 $n$ 代表有多少个人参赛。

接下来一行 $n$ 个数，代表序列，保证给出的序列是存在的。

输出格式

输出这个序列是第几大的，答案 $\bmod 1000007$。

3
1 2 2

4

样例解释

有三个人，假设他们叫 A、B、C。

当为 (A, B, C) 时，序列为 $1,1,1$；
当为 (A, B)，(C) 时，序列为 $1,1, 2$；
当为 (A, C)，(B) 时，序列为 $1, 2, 1$；
当为 (A)，(B, C) 时，序列为 $1,2,2$；
当为 (A)，(B)，(C) 时，序列为 $1,2,3$。

所以，$1,2,2$ 是第 $4$ 大的。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^4$。