Joyful KMP

Hongjun recently learned the KMP (Knuth-Morris-Pratt) algorithm and is stuck on understanding the failure function. For a string $S = s_1s_2\cdots s_N$, its failure function consists of $N$ values $f[1], f[2], \cdots, f[N]$, where $f[i]$ is the length of the longest string that is both a proper prefix and a suffix of $s_1s_2\cdots s_i$. If no such string exists, $f[i]$ is $0$. For example, the failure function of abcabd is shown in the table below.

To understand the failure function better, Hongjun picked a string and wants to list, in lexicographic order, every string made only of lowercase English letters that has the same failure function. You decide to help him. Write a program that counts the strings with the same failure function as the given string and finds the $K$-th one in lexicographic order.

The first line contains a string of length between 1 and $10^6$, inclusive. The string consists only of lowercase English letters.

The second line contains a single positive integer $K$ ($1 \le K \le 9 \times 10^{18}$).

On the first line, print the number of lowercase strings that have the same failure function as the input string, modulo $1\,000\,000\,007$. This number can be very large.

On the second line, print the string that comes $K$-th in lexicographic order among those strings. If there are fewer than $K$ such strings, print OVER.

Only strings in which the first and third characters are equal, the second and fourth characters are equal, and the first and second characters differ have the same failure function as abab. So the number of such strings is $26 \times 25 = 650$.

The 100th string in lexicographic order is dzdz.