AT_arc131_f [ARC131F] ARC Stamp

从仅由 `A`、`R`、`C` 组成的字符串 $S$ 开始，进行不超过 $K$ 次“选择连续的三个字符并将其覆盖为 `ARC`”的操作后，得到了字符串 $T$。 请问，作为初始字符串 $S$，有多少种可能？请输出这个数对 $998244353$ 取模的结果。

输入以以下格式从标准输入给出。 > $T$ $K$

请输出答案。

## 限制条件 - $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$。 由 ChatGPT 4.1 翻译