수행평가 1

재현이는 알고리즘 수행평가 과제로 길이가 $N$인 수열 $A$를 냈다. $A$의 모든 원소는 $M$ 이하의 자연수다. 재현이는 모든 원소가 $M$ 이하인 수열을 아름다운 수열이라고 부른다.

재현이는 자신만의 아름다운 수열 $B$를 하나 더 만들어 내려고 한다. $B$의 원소도 모두 $1$ 이상 $M$ 이하의 자연수이고, 길이는 $1$ 이상이다. 선생님은 $B$가 $A$의 연속된 부분 수열이면 표절로 판단하므로, $B$는 $A$ 안에 연속으로 등장하면 안 된다.

시간이 없는 재현이는 길이가 가장 짧은 $B$를 만들려고 한다. 조건을 만족하는 $B$의 최소 길이와, 그 길이를 가지는 $B$의 개수를 $10^9 + 7$로 나눈 나머지를 구하여라. 길이가 $N + 1$인 수열은 $A$ 안에 연속으로 등장할 수 없으므로 답은 항상 존재한다.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 100000$)

둘째 줄에 수열 $A$의 원소 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le M$)

첫째 줄에 조건을 만족하는 $B$의 최소 길이와, 그 길이를 가지는 $B$의 개수를 $10^9 + 7$로 나눈 나머지를 공백으로 구분해 출력한다.