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}, \dots, S^m_{i+n-1}]$ 之间的汉明距离（其中 $1 \le i \le |S^m| - n + 1$）。

Helena 想要找到 $f(i)$ 的最小值，以及 $f(i)$ 的总和对 $(10^9 + 7)$ 取模的结果。

注意：两个等长序列之间的汉明距离是指对应位置上元素不同的位置数量。

输入格式

输入包含多组测试数据，以文件结束符（EOF）终止。 每组测试数据的第一行包含两个整数 $n$ 和 $m$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

• $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$。

输出格式

对于每组测试数据，输出两个整数，分别表示 $f(i)$ 的最小值和 $f(i)$ 的总和对 $(10^9 + 7)$ 取模的结果。

样例

样例输入 1

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

样例输出 1

1 9
1 7
0 7