#4798. [Ceoi2015]Calvinball championship

内存限制:256 MiB 时间限制:20 Sec

题目描述

有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。(具体意思见样例解释)

输入格式

第一行一个n代表有多少个人参赛
接下来一行n个数,代表序列
n<=10000,保证给出的序列是存在的

输出格式

输出这个序列是第几大的,mod 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大的

数据范围与提示