제목 설명

토끼는 당근을 즐겨 먹는다. 토끼는 땅을 파서 $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$입니다.