打怪兽2

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

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

游戏的规则是这样的。

度度熊一开始会有一个初始的能量值。每次遇到一个怪兽,若度度熊的能量值$\geq$ 怪兽的能量值并且度度熊剩余血量$\geq$怪兽的攻击力,那么怪兽将会被打败,度度熊的能量值增加1,度度熊的血量减少该怪兽的攻击力,否则度度熊死亡(度度熊的血量刚好减到0时并不会死亡,还能继续战斗),游戏结束。

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

共有n个怪兽,由于度度熊比较弱,它一开始只有1点能量值。
n个怪兽排列随机,也就是说共有n!种可能,度度熊想知道结束时它能量值的期望。
注意这里怪兽的编号是从1开始到编号n为止且编号为i的怪兽能量值为i-1。

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

在样例中有5个怪兽,它们的能量分别为0,1,2,3,4,其中每个怪兽的攻击力都为1。

Input

多组数据。对于每一组数据:
第一行两个数n,m表示有n只怪兽,度度熊的初始血量(1<=n<=500000,1<=m<=10^9)。

接下来一行n个数ai表示编号为i的怪兽的攻击力(0<=ai<=m)。

Output

一行表示答案。

Sample Input

5 4 1 1 1 1 1

Sample Output

104

Hint

liuyiding

Source

2017"百度之星"程序设计大赛 - 初赛(B)

提交代码