407309: GYM102759 G 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$$$.

ACAYKP
0

1

CAPCAK
1

896

WEDONTNEEDNOEDUCATION
2

24651976

WEDONTNEEDNOTHOUGHTCONTROL
3

224129308