ABC 对称性

时间限制：2s
空间限制：1024MB

题目描述

对于一个仅由 A、B、C 组成的非空字符串 $T$，如果可以按任意顺序执行任意多次以下操作，将它变成空字符串，就称 $T$ 为好字符串：

• 选择两个相同的字符并删除；
• 各选择一个 A、一个 B、一个 C 并删除。

例如，ABACA 是好字符串：先各删除一个 A、B、C，剩下 AA，再删除两个 A 即可。

给定一个长度为 $N$、由 A、B、C、? 组成的字符串 $S$。将每个 ? 分别替换为 A、B 或 C 后，求有多少个得到的字符串包含至少 $K$ 个是好字符串的连续子串。同一内容的子串只要位置不同，就分别计数。

答案对 $998244353$ 取模。

输入格式

N K
S

输出格式

输出满足条件的替换方案数对 $998244353$ 取模的结果。

样例输入 1

4 2
A?AB

样例输出 1

1

样例说明 1

三个可能的字符串是 AAAB、ABAB、ACAB。其中只有 AAAB 至少含有两个好子串。

样例输入 2

50 411
??AB??C???????????????????????????????A???C????A??

样例输出 2

457279314

样例输入 3

1 0
A

样例输出 3

1

数据范围

• $1\le N\le50$；
• $0\le K\le\dfrac{N(N+1)}2$；
• $\vert S\vert =N$；
• $S$ 仅由 A、B、C、? 组成。