8798: BZOJ4798：[Ceoi2015]Calvinball championship

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

提示

没有写明提示

题目来源

没有写明来源