해밍 거리

Helena는 다음 규칙으로 수열의 목록을 만들었다.

$S^1 = [1]$

$S^2 = S^1 + [2] + S^1$

$S^3 = S^2 + [3] + S^2$

$\dots$

$S^m = S^{m-1} + [m] + S^{m-1}$

여기서 $A+B$는 수열 $A$와 $B$를 이어 붙인 수열이다.

주어진 수열 $[a_1, a_2, \dots, a_n]$에 대해, $f(i)$를 $[a_1, a_2, \dots, a_n]$과 $[S^m_i, S^m_{i+1}, \ldots, S^m_{i+n-1}]$의 해밍 거리로 정의한다 ($1 \le i \le |S^m| - n + 1$).

$f(i)$의 최솟값과 모든 $f(i)$의 합을 $(10^9+7)$로 나눈 나머지를 구하라.

길이가 같은 두 수열의 해밍 거리는 대응하는 원소가 서로 다른 위치의 개수이다.

입력은 여러 개의 테스트 케이스로 이루어지며, 파일의 끝에서 끝난다.

첫 줄에 두 정수 $n$과 $m$이 주어진다.

둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다.

각 테스트 케이스마다 $f(i)$의 최솟값과 $f(i)$의 합을 $(10^9+7)$로 나눈 나머지를 두 정수로 출력한다.

$1 \le m \le 10^5$

$1 \le n \le \min(|S^m|, 10^5)$

$1 \le a_i \le m$

모든 테스트 케이스의 $n$의 합은 $2 \times 10^6$을 넘지 않는다.