分数: 500 点
问题陈述
对于非空字符串 T 组成 A, B,和 C,如果可以通过以任意顺序执行任意次数的以下两种操作将其变成空字符串,我们称其为好字符串。
- 操作 1:选择字符串中两个相同的字符并将其删除(如果没有两个或多个相同的字符则无法执行)。
- 操作 2:选择一项
A,一B,和一个 将字符串中的C删除(如果其中每一个都不存在,则无法执行A,B,和C).
例如, ABACA 是一个很好的字符串,因为可以通过执行以下操作将其转换为空字符串:
- 选择第2、4、5个字符并将其删除(操作 2)。字符串变成
AA. - 选择第1个和第2个字符并将其删除(操作 1)。该字符串变为空字符串。
给你一个字符串 S 长度 N 组成 A, B, C,和 ?。分别有多少种替换方式 ? 与 A, B,或 C 形成一个包含以下内容的字符串 至少 K 好的字符串作为连续子字符串?如果子字符串位于原始字符串中的不同位置,即使它们是相同的字符串,也会单独计数。
求计数模数 998244353.
约束
- 1 \leq N \leq 50
- 0 \leq K \leq \frac{N(N+1)}{2}
- N 和 K 是整数。
- |S| = N
- S 是一个由以下组成的字符串
A,B,C,和?.
输入
输入由标准输入按以下格式给出:
N K S
输出
打印答案模数 998244353.
示例输入 1
4 2 A?AB
示例输出 1
1
通过替换 ? 与 A, B,或 C,我们可以得到以下三个字符串: AAAB, ABAB, ACAB.
其中, AAAB 包含两个好的子字符串: AA 在位置 1,2 和 AA 在位置 2,3。请注意,即使子字符串与字符串相同,如果它们位于原始字符串中的不同位置,也会单独计数。
另一方面, ABAB 只包含一个好的子字符串 ABAB。另外, ACAB 只包含一个好的子字符串 CAB.
示例输入 2
50 411 ??AB??C???????????????????????????????A???C????A??
示例输出 2
457279314
打印计数模数 998244353.
示例输入 3
1 0 A
示例输出 3
1