分数: 1000 点
问题陈述
在一根绳子上 S 组成 A, R,和 C,我们最多做了以下操作 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 从中我们可以得到字符串 T = ARCCARC 最多 1 操作。
- S =
ARCCARC:我们可以选择什么都不做来获取ARCCARC. - S =
CRACARC:我们可以选择 1-st, 2-nd, 3-rd 字符并用以下内容覆盖它们ARC得到ARCCARC. - S =
ARCCCCC:我们可以选择 5-th, 6-th, 7-th 个字符并将其覆盖为ARC得到ARCCARC.
还有许多其他字符串可以 S,总共 53.
示例输入 2
ARARCRCA 5
示例输出 2
2187
如果初始字符串 S is AAAAAAAA,一种获取方式 T = ARARCRCA 最多 5 操作如下。
- 步骤 1:选择 3-rd, 4-th, 5-th 个字符并将其覆盖为
ARC获取字符串AAARCAAA. - 步骤 2:选择 5-th, 6-th, 7-th 个字符并将其覆盖为
ARC获取字符串AAARARCA. - 步骤 3:选择 1-st, 2-nd, 3-rd 字符并用以下内容覆盖它们
ARC获取字符串ARCRARCA. - 步骤 4:选择 3-rd, 4-th, 5-th 个字符并将其覆盖为
ARC获取字符串ARARCRCA.
还有许多其他字符串可以 S,总共 2187.
示例输入 3
AARCRRARCC 0
示例输出 3
1
我们可以得到 T = AARCRRARCC 与 0 仅在一种情况下进行操作 S = T 从头开始,或 S = AARCRRARCC.
示例输入 4
AAAAARRRRRCCCCC 131
示例输出 4
1
在这种情况下,只有一个字符串可以是 S: AAAAARRRRRCCCCC.
示例输入 5
CAARCACRAAARARARCRCRARCARARCRRARC 9
示例输出 5
797833187
有 320236026147 字符串可能是 S,所以打印这个计数模 998244353,即 797833187.