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$.