题目描述

小白兔爱吃胡萝卜，它将土地挖成了$M$个坑排成一排，从左到右按$1$-$M$编号，每个坑里可以种一个胡萝卜，在$N$天内小兔都会凭心情选择一个坑种胡萝卜，如果已经被占用，则会种在前一个坑里，如果依然被占用，小白兔会再往前找空的坑，直到找到空的坑或者发现前面没有可用的坑为止。

你本来需要输出$N$行，每一行表示当天的胡萝卜将种在哪一个坑里(无法种下输出$0$)，但为了避免输出占用过多的时间，你只需要输出($1\times$第一天$+2\times$第二天$+……+N\times$第$N$天)$\mod1000000007$的结果即可)

输入格式

第一行两个整数$N,M$

接下来一个$N$个整数，表示当天小兔选择的坑

输出格式

一行，一个整数，意义如题目描述

样例

5 8
7 7 1 6 1

42

数据规模与约定

对于$30\%$的数据，$N,M\le 1000$；

对于$70\%$的数据，$N,M\le 200000$；

对于$100\%$的数据，$N,M\le 3000000$。