Title Description

The little white rabbit loves to eat carrots. It excavates the land into $M$ pits and arranges them in a row. From left to right, it presses the $1- M$ numbers to plant one carrot in each pit. Within N days, the little rabbit will choose a pit based on its mood to plant carrots. If it is already occupied, it will plant in the previous pit. If it is still occupied, the little white rabbit will search for empty pits until it finds an empty pit or finds no available pit ahead.

You originally needed to output $N$ rows, each row representing which pit the carrots for that day will be planted in (unable to plant output $0$), but to avoid output taking up too much time, you only need to output the result of ($1\times$first day $+2 \times$second day $+...+N \times$ $N$-th day ) $\mod 1000000007$)

Input format

The first line consists of two integers $N, M$.

The next $N$ integers represent the pit chosen by the little rabbit on that day.

Output format

One line, one integer, meaning as described in the title

Example

5 8
7 7 1 6 1

42

Data scale and agreement

For data of $30\%$, $N, M \le 1000$;

For data of $70\%$, $N, M \le 200000$;

For data of $100\%$, $N, M\le 3000000$.