題目描述

小白兔愛吃胡蘿蔔，它將土地挖成了$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$。