즐거운 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$보다 작은 것 가운데 가장 긴 것의 길이이다. 그런 문자열이 없으면 $f[i]$는 $0$이다. 예를 들어 abcabd의 실패 함수는 아래 표와 같다.

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

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

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

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

두 번째 줄에는 그러한 문자열을 사전 순으로 나열했을 때 $K$번째에 오는 문자열을 출력한다. $K$가 너무 커서 그런 문자열이 존재하지 않으면 OVER를 출력한다.

첫 번째 문자와 세 번째 문자가 같고, 두 번째 문자와 네 번째 문자가 같으며, 첫 번째 문자와 두 번째 문자가 다른 꼴의 문자열만이 abab와 실패 함수가 같다. 따라서 그러한 문자열의 개수는 $26 \times 25 = 650$이다.

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