20027번 - LCS 8 다국어

문제

You are given a string $S$ of length $N,ドル consisting of uppercase letters, and a small nonnegative integer $K$.

Please compute the number of strings $T$ of length $N,ドル consisting of only uppercase letters, such that the longest common subsequence of $S$ and $T$ has length at least $N - K$. As the number could be large, print the number of such strings modulo 10ドル^9 + 7$.

A string $S = s_1s_2\ldots s_n$ is a subsequence of a string $T = t_1t_2\ldots t_m$ if there exists an increasing sequence of indices 1ドル \le i_1 < i_2 < \ldots < i_n \le m$ such that $s_x = t_{i_x}$ for all 1ドル \le x \le n$.

입력

The first line of the input contains the length-$N$ string $S$ (1ドル \le |S| \le 50,000円$). All characters of $S$ are uppercase letters.

The next line of the input contains the single integer $K$ (0ドル \le K \le 3)$.

출력

Print the number of such strings modulo 10ドル^9 + 7$.

제한

힌트