시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

## 문제

Helena has generated a list of sequences:

\begin{aligned} 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} \end{aligned}

where $A+B$ means the concatenation of two sequences $A$ and $B$.

For a given sequence $[a_1,a_2,\dots,a_n]$, let $f(i)$ be the Hamming distance between $[a_1,a_2,\dots,a_n]$ and $[S^m_i, S^m_{i+1}, \ldots, S^m_{i+n-1}]$ ($1 \le i \le |S^m| - n + 1)$.

Helena would like to find the minimum value of $f(i)$ and the sum of $f(i)$ modulo $(10^9+7)$.

Note that the Hamming distance between two sequences of equal length is the number of positions at which the corresponding elements are different.

## 입력

The input consists of several test cases terminated by end-of-file.

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$.

## 출력

For each test case, output two integers denoting the minimum value of $f(i)$ and the sum of $f(i)$ modulo $(10^9+7)$.

## 제한

• $1 \le m \leq 10^5$
• $1 \leq n \leq \min(|S^m|, 10^5)$
• $1 \leq a_i \leq m$
• The sum of $n$ does not exceed $2 \times 10^6$.

## 예제 입력 1

3 3
1 2 3
3 3
1 1 1
3 3
1 2 1


## 예제 출력 1

1 9
1 7
0 7