题目描述

给定由 A、R 和 C 组成的字符串 $S$，我们进行如下操作，最多不超过 $K$ 次：选择三个连续的字符并用 ARC 替换它们。结果产生了字符串 $T$。

有多少个字符串可能是初始字符串 $S$？计算这个计数的模 $998244353$ 值。

约束条件

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

---

输入

从标准输入中以以下格式给出输入：

$T$ $K$

输出

输出答案。

---

示例输入1

ARCCARC
1

示例输出1

53

以下是一些可能的初始字符串 $S$ 的示例，最多使用 $1$ 次操作可以得到字符串 $T$ = ARCCARC。

• $S$ = ARCCARC：我们可以选择不做任何操作，得到 ARCCARC。
• $S$ = CRACARC：我们可以选择第 1、2、3 个字符，并用 ARC 覆盖它们，得到 ARCCARC。
• $S$ = ARCCCCC：我们可以选择第 5、6、7 个字符，并用 ARC 覆盖它们，得到 ARCCARC。

还有很多其他可能的字符串可以作为 $S$，总共有 $53$ 个。

---

示例输入2

ARARCRCA
5

示例输出2

2187

如果初始字符串 $S$ 是 AAAAAAAA，使用最多 $5$ 次操作得到 $T$ = 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

AARCRRARCC
0

示例输出3

1

我们可以在只有一种情况下使用 $0$ 次操作得到 $T$ = AARCRRARCC，即 $S = T$，或者 $S$ = AARCRRARCC。

---

示例输入4

AAAAARRRRRCCCCC
131

示例输出4

1

在这种情况下，只有一个可能的字符串 $S$：AAAAARRRRRCCCCC。

---

示例输入5

CAARCACRAAARARARCRCRARCARARCRRARC
9

示例输出5

797833187

有 $320236026147$ 个可能的字符串 $S$，所以输出模 $998244353$ 的结果为 $797833187$。