20795번 - Hamming Distance 다국어

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$.