부분 수열이 아닌 최단 문자열

시간 제한2초메모리 제한256 MB

요약

알파벳 크기 k와 문자열 s가 주어질 때 s의 부분 수열이 아닌 가장 짧은 문자열의 길이와 그 개수를 1e9+7로 나눈 나머지를 구합니다.

난이도: 보통10점 중 6점
유형: 그리디, 문자열, 조합론
정답자: 아직 제출이 없습니다

문제

이 문제에서 크기가 $k$ 인 알파벳은 아래 리스트의 처음 $k$ 개 글자를 말한다.

a, b, c, ..., z, A, B, C, ..., Z, 0, 1, ..., 9

각 테스트 케이스마다 $k$ 가 주어지고, 크기가 $k$ 인 알파벳만 고려한다.

문자열 $t[1..m]$ 이 문자열 $s[1..n]$ 의 부분 수열이려면 $t[1] = s[i_1]$ , $t[2] = s[i_2]$ , ..., $t[m] = s[i_m]$ 을 만족하는 인덱스 $1 \le i_1 < i_2 < \cdots < i_m \le n$ 이 존재해야 한다. 예를 들어 acb는 babcaab의 부분 수열이다.

문자열 $s[1..n]$ 이 주어졌을 때, $s$ 의 부분 수열이 아닌 문자열 $t[1..m]$ 중 $m$ 이 가장 작은 것을 찾고, 그런 문자열이 몇 개인지 세는 프로그램을 작성하시오. $t$ 는 크기가 $k$ 인 알파벳의 글자로만 이루어진다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ ( $1 \le T \le 100$ )가 주어진다. 이어지는 각 줄에 알파벳의 크기 $k$ ( $1 \le k \le 62$ )와 문자열 $s[1..n]$ ( $1 \le n \le 10^6$ )이 공백으로 구분되어 주어진다. $s$ 는 위 리스트의 글자로만 이루어져 있다.

출력

각 테스트 케이스마다 두 정수를 한 줄에 출력한다. 첫 번째 정수는 가장 작은 $m$ 이고, 두 번째 정수는 그런 문자열 $t[1..m]$ 의 개수를 $10^9 + 7$ 로 나눈 나머지이다.

예제2

예제 1

입력

3
2 abba
62 0123456789
3 aabbcbbcbabcbab

예상 출력

3 5
1 52
4 7

예제 2
입력
```
2
1 a
1 aaaaa
```
예상 출력
```
2 1
6 1
```