给定一个长度为 $N$ 的字符串 $S$，由大写字母组成，以及一个较小的非负整数 $K$。

请计算有多少个长度为 $N$ 的大写字母字符串 $T$，使得 $S$ 和 $T$ 的最长公共子序列长度至少为 $N - K$。由于结果可能很大，请输出该数量对 $10^9 + 7$ 取模的结果。

字符串 $S = s_1s_2 \dots s_n$ 是字符串 $T = t_1t_2 \dots t_m$ 的子序列，当且仅当存在一个递增的下标序列 $1 \le i_1 < i_2 < \dots < i_n \le m$，使得对于所有 $1 \le x \le n$，都有 $s_x = t_{i_x}$。

输入格式

第一行包含一个长度为 $N$ 的字符串 $S$ ($1 \le |S| \le 50\,000$)。$S$ 中的所有字符均为大写字母。

第二行包含一个整数 $K$ ($0 \le K \le 3$)。

输出格式

输出满足条件的字符串数量，对 $10^9 + 7$ 取模。

样例

样例输入 1

ACAYKP
0

样例输出 1

1

样例输入 2

CAPCAK
1

样例输出 2

896

样例输入 3

WEDONTNEEDNOEDUCATION
2

样例输出 3

24651976

样例输入 4

WEDONTNEEDNOTHOUGHTCONTROL
3

样例输出 4

224129308