← 返回题目列表

AtCoder · arc131_f

F. ARC 印章

中文机器翻译题面 查看原题

分数: 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.