当前没有测试数据。

Description

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

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

Format

Input

第一行两个整数N,M

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

Output

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

Samples

input1

5 8
7 7 1 6 1

output1

42

Limitation

数据规模与约定

对于 30% 的数据N，M≤1000；

对于 70%的数据，N，M≤200000；

对于 100%的数据，N，M≤3000000。

时间限制：1s

空间限制：128MB