G. LCS 8
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt i_2 \lt \ldots \lt i_n \le m$$$ such that $$$s_x = t_{i_x}$$$ for all $$$1 \le x \le n$$$.

Input

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

Output

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

Examples
Input
ACAYKP
0
Output
1
Input
CAPCAK
1
Output
896
Input
WEDONTNEEDNOEDUCATION
2
Output
24651976
Input
WEDONTNEEDNOTHOUGHTCONTROL
3
Output
224129308