시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (추가 시간 없음) 1024 MB 17 6 6 100.000%

문제

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

예제 입력 1

ACAYKP
0

예제 출력 1

1

예제 입력 2

CAPCAK
1

예제 출력 2

896

예제 입력 3

WEDONTNEEDNOEDUCATION
2

예제 출력 3

24651976

예제 입력 4

WEDONTNEEDNOTHOUGHTCONTROL
3

예제 출력 4

224129308

출처

University > KAIST > 2020 KAIST 10th ICPC Mock Competition E번