시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 14 8 6 66.667%

문제

최재현은 이번 알고리즘 수행 평가를 위한 문제를 만들지 못한 관계로, 선생님께 대신 길이가 N인 수열 A를 뇌물로 드렸다.

수열 A는 길이가 N이며, M보다 작거나 같은 자연수로 이루어진 수열이다. 재현이는 모든 원소가 M보다 작거나 같은 수열을 아름답다고 생각하고, 선생님도 그렇게 생각할 거라고 생각해서 이를 뇌물로 드렸다. 

애석하게도, 구재현 역시 이번 알고리즘 수행 평가를 위한 문제를 만들지 못했고, 급해진 재현이는 빨리 자신만의 아름다운 수열 B를 만들어서 선생님께 드리려고 결심했다.

하지만, 선생님은 이미 재현이에게 아름다운 수열 A를 받았고 충분히 감동하신 상태이다. 선생님은 재현이가 준 수열 B가 "재현이의 수열 A의 부분 수열이라면" 재현이의 수열이 표절이라고 판단하고 재현이에게 F를 줄 예정이다. 

시간이 없는 재현이는, 수열의 길이를 최소화해서 선생님에게 드릴 예정이다. 재현이가 만들 수 있는 수열의 최소 길이와, 해당 길이를 가지는 수열의 개수를 10^9 + 7로 나눈 나머지를 출력하라.

입력

첫번째 줄에 N, M이 주어진다. (1 <= N, M <= 100000)

두번째 줄에 N개의 정수 Ai가 주어진다. (1 <= Ai <= M)

출력

수열의 최소 길이와, 그러한 수열의 개수를 10^9 + 7로 나눈 나머지를 출력하라.

예제 입력

8 2
1 2 1 1 2 2 2 2

예제 출력

3 1

예제 입력 2

4 5
1 2 3 4

예제 출력 2

1 1

예제 입력 3

6 3
1 2 3 3 2 1

예제 출력 3

3 14

힌트

출처