lyk在玩一个叫做“打怪兽”的游戏。

游戏的规则是这样的。

lyk一开始会有一个初始的能量值。每次遇到一个怪兽，若lyk的能量值>=怪兽的能量值，那么怪兽将会被打败，lyk的能量值增加1，否则lyk死亡，游戏结束。

若怪兽全部打完，游戏也将会结束。

共有n个怪兽，由于lyk比较弱，它一开始只有0点能量值。

n个怪兽排列随机，也就是说共有n!种可能，lyk想知道结束时它能量值的期望。

由于小数点比较麻烦，所以你只需要输出期望*n!关于1000000007取模后的值就可以了！

 

例如有两个怪兽，能量值分别为{0,1}，那么答案为2，因为游戏结束时有两种可能，lyk的能量值分别为0和2。期望为1,1*2!=2，所以答案为2。

Input

第一行一个数n(1<=n<=100000)。接下来一行n个数ai表示怪兽的能量(0<=ai

Output

一行表示答案

Input示例

20 1

Output示例

2 思路： 每轮打败怪兽后 lyk的能量值加一  　　　 所以 我们可以看出来 如果lyk在第i轮 打败一个怪兽 那么在第i+1轮也一定可以打败这个怪兽 　　　 我们设 dp[i] 表示 lyk活到第 i 轮的概率  这时候lyk的能量 必然为i 　　　 显然 第 i 轮 lyk一定存活 所以 dp[0] = N! %Mod 　　　 假设 我们已知 dp[i] 看一下怎么表示第 i+1轮的概率 　　　 x 表示 有多少怪兽的能量小于等于 i+1 　　　 到了 第 i+1 轮 只剩 (x-(i+1)+1) 只怪兽可以打 总的怪兽还剩 (n-(i+1)+1) 只 　　　 第i+1轮存活的概率记为 (x-(i+1)+1)/(n-(i+1)+1) 　　　 那么到第 i+1 轮仍然存活的概率为 dp[i] *(x-(i+1)+1)/(n-(i+1)+1) 　　　 除法用逆元来计算即可

1 #include
         
           2 #include
          
            3 #include
           
             4 #include
            
              5 #include
             
               6  7 #define MAXN 50005 8  9 #define Mod 100000000710 11 using namespace std;12 13 typedef long long LL;14 15 LL num[100005],dp[100005];16 17 LL Fast_Pow(LL a) {18     LL ret = 1, b = Mod - 2;19     while(b) {20         if (b & 1) ret = ( ret * a ) % Mod;21         a = ( a * a ) % Mod, b >>= 1;22     }23     return ret;24 }25 26 int main(int argc,char *argv[]) {27     int n; scanf("%d",&n);28     for(int i=0; i
              
               =num[j] && j