25029번 - Joyful KMP

최근 KMP(Knuth-Morris-Pratt)알고리즘을 배운 홍준이는 실패함수의 이해에 대해서 골몰하고 있다. 어떤 문자열 $S = s_1s_2\cdots s_N$에 대해, 이 문자열의 실패함수는 $N$개의 값 $f[1], f[2], \cdots , f[N]$으로 나타나며, $f[i]$는 $s_1s_2\cdots s_i$의 접두사가 되면서 동시에 접미사가 되는 길이 $i$미만의 문자열 중 가장 긴 것의 길이이다. 만약 그런 문자열이 없다면 $0$을 가진다. 예를 들어, $S = $"abcabd"의 실패함수는 다음과 같다.

홍준이는 실패함수를 이해하기 위해서 어떤 문자열을 하나 놓고, 이 문자열과 같은 실패함수를 가지는 알파벳 소문자 만으로 이루어진 문자열을 모두 구해 사전 순으로 나열하려고 한다. 옆에서 지켜보던 당신은 홍준이를 도와 주어진 문자열과 같은 실패함수를 가지는 문자열의 개수와 그 중 사전 순으로 $K$번째인 문자열을 구해주는 프로그램을 작성하기로 했다.

첫 번째 줄에 길이가 $1$이상 $10^6$이하인 문자열이 주어진다. 이 문자열은 알파벳 소문자 만으로 이루어져 있다.

두 번째 줄에 하나의 양의 정수 $K$($ 1 ≤ K ≤ 9 \times 10^{18}$)가 주어진다.

첫 번째 줄에는 입력으로 주어진 문자열과 같은 실패 함수를 가지는 알파벳 소문자 만으로 이루어진 문자열의 개수를 출력한다. 이 수는 매우 클 수 있으므로, $1\,000\,000\,007$로 나눈 나머지를 출력하도록 한다.

두 번째 줄에는 입력으로 주어진 문자열과 같은 실패 함수를 가지는 알파벳 소문자 만으로 이루어진 문자열 중에서 사전 순으로 $K$번째에 오는 문자열을 출력한다. $K$가 너무 커서 이런 문자열이 존재하지 않는다면 “OVER”를 출력한다.

첫 번째 문자와 세 번째 문자가 같고, 두 번째 문자와 네 번째 문자가 같고, 첫 번째 문자와 두 번째 문자가 다른 꼴의 문자열만이 입력으로 주어진 문자열과 실패함수가 같다. 그러므로 $26 \times 25 = 650$이 abab와 실패함수가 같은 문자열의 개수이다.

그 중에서 사전 순으로 $100$번째에 오는 문자열은 dzdz이다.