题目描述

从仅由 A、R、C 组成的字符串 $S$ 开始，进行不超过 $K$ 次“选择连续的三个字符并将其覆盖为 ARC”的操作后，得到了字符串 $T$。

请问，作为初始字符串 $S$，有多少种可能？请输出这个数对 $998244353$ 取模的结果。

输入格式

输入以以下格式从标准输入给出。

$T$ $K$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

ARCCARC
1

输出 #1

53

输入输出样例 #2

输入 #2

ARARCRCA
5

输出 #2

2187

输入输出样例 #3

输入 #3

AARCRRARCC
0

输出 #3

1

输入输出样例 #4

输入 #4

AAAAARRRRRCCCCC
131

输出 #4

1

输入输出样例 #5

输入 #5

CAARCACRAAARARARCRCRARCARARCRRARC
9

输出 #5

797833187

说明/提示

限制条件

• $3 \leq |T| \leq 5000$
• $0 \leq K \leq 10000$
• $T$ 是仅由 A、R、C 组成的字符串

样例解释 1

例如，初始字符串 $S$ 可能如下所示，在不超过 $1$ 次操作后可以得到字符串 $T = \texttt{ARCCARC}$。

• 当 $S = \texttt{ARCCARC}$ 时：无需操作即可得到字符串 ARCCARC。
• 当 $S = \texttt{CRACARC}$ 时：选择第 $1,2,3$ 个字符覆盖为 ARC，即可得到 ARCCARC。
• 当 $S = \texttt{ARCCCCC}$ 时：选择第 $5,6,7$ 个字符覆盖为 ARC，即可得到 ARCCARC。 除此之外还有很多其他可能，作为 $S$ 的方案共有 $53$ 种。

样例解释 2

当初始字符串 $S = \texttt{AAAAAAAA}$ 时，例如可以通过如下不超过 $5$ 次的操作得到字符串 $T = \texttt{ARARCRCA}$。

• 第 $1$ 步：选择第 $3,4,5$ 个字符覆盖为 ARC，得到 AAARCAAA。
• 第 $2$ 步：选择第 $5,6,7$ 个字符覆盖为 ARC，得到 AAARARCA。
• 第 $3$ 步：选择第 $1,2,3$ 个字符覆盖为 ARC，得到 ARCRARCA。
• 第 $4$ 步：选择第 $3,4,5$ 个字符覆盖为 ARC，得到 ARARCRCA。 除此之外还有很多其他可能，作为 $S$ 的方案共有 $2187$ 种。

样例解释 3

若 $0$ 次操作即可得到字符串 $T = \texttt{AARCRRARCC}$，只有初始时 $S = T$，即 $S = \texttt{AARCRRARCC}$ 这一种情况。

样例解释 4

在本输入样例中，作为 $S$ 的可能只有 $\texttt{AAAAARRRRRCCCCC}$ 这一种。

样例解释 5

作为初始字符串 $S$ 的可能有 $320236026147$ 种，因此输出 $320236026147$ 对 $998244353$ 取模的结果 $797833187$。