Performance Assessment 1

Jaehyun handed in a sequence $A$ of length $N$ for his algorithm assignment. Every element of $A$ is a natural number at most $M$. He calls a sequence beautiful when all of its elements are at most $M$.

Jaehyun wants to hand in one more beautiful sequence $B$ of his own. Every element of $B$ is also a natural number between $1$ and $M$, and its length is at least $1$. The teacher rules that $B$ is plagiarism if $B$ is a contiguous subsequence of $A$, so $B$ must not appear inside $A$ as a contiguous block.

Jaehyun has no time left, so he wants $B$ to be as short as possible. Find the minimum length of a sequence $B$ that satisfies the condition, and the number of sequences of that length, modulo $10^9 + 7$. A sequence of length $N + 1$ can never appear inside $A$ as a contiguous block, so an answer always exists.

The first line contains $N$ and $M$, separated by a space. ($1 \le N, M \le 100000$)

The second line contains the elements $A_1, A_2, \dots, A_N$ of the sequence $A$, separated by spaces. ($1 \le A_i \le M$)

Print the minimum length of a sequence $B$ that satisfies the condition and the number of sequences of that length modulo $10^9 + 7$, separated by a space.