LCS 8

대문자로만 이루어진 길이 $N$의 문자열 $S$와 작은 음이 아닌 정수 $K$가 주어진다. 대문자로만 이루어진 길이 $N$의 문자열 $T$ 중에서 $S$와 $T$의 최장 공통 부분 수열(LCS)의 길이가 $N - K$ 이상인 것의 개수를 구하라. 개수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

문자열 $S = s_1s_2\ldots s_n$이 문자열 $T = t_1t_2\ldots t_m$의 부분 수열이라는 것은, 모든 $1 \le x \le n$에 대해 $s_x = t_{i_x}$를 만족하는 증가하는 인덱스 수열 $1 \le i_1 < i_2 < \ldots < i_n \le m$이 존재한다는 뜻이다.

첫째 줄에 대문자로만 이루어진 길이 $N$의 문자열 $S$가 주어진다. 길이는 $1 \le |S| \le 50\,000$을 만족한다.

둘째 줄에 정수 $K$가 주어진다. $0 \le K \le 3$을 만족한다.

조건을 만족하는 문자열 $T$의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.