Description

有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。

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

Format

Input

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

接下来一行n个数，代表序列

n<=10000，保证给出的序列是存在的

Output

输出这个序列是第几大的，mod 1000007。

Samples

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大的