AT_arc188_a [ARC188A] ABC Symmetry

对于由 `A`、`B`、`C` 组成的非空字符串 $T$，如果可以以任意顺序、任意次数地进行以下两种操作，使其变为空字符串，则称其为“好字符串”。 - 操作 $1$：从字符串中选择两个相同的字符并删除（如果没有两个及以上相同的字符则无法进行此操作）。 - 操作 $2$：从字符串中各选择一个 `A`、一个 `B`、一个 `C` 并删除（如果 `A`、`B`、`C` 各至少有一个才可进行此操作）。 例如，`ABACA` 可以通过如下操作变为空字符串，因此是好字符串。 - 选择第 $2,4,5$ 个字符删除（操作 $2$），字符串变为 `AA`。 - 选择第 $1,2$ 个字符删除（操作 $1$），字符串变为空字符串。 给定一个由 `A`、`B`、`C`、`?` 组成、长度为 $N$ 的字符串 $S$。将每个 `?` 替换为 `A`、`B` 或 `C` 后，问有多少种字符串，包含至少 $K$ 个连续的好字符串作为子串。注意，即使是相同的子串，只要在原字符串中的位置不同，也要分别计数。 请输出答案对 $998244353$ 取模后的结果。

输入以如下格式从标准输入读入。 > $N$ $K$ $S$

请输出答案对 $998244353$ 取模后的整数。

### 限制条件 - $1 \leq N \leq 50$ - $0 \leq K \leq \frac{N(N+1)}{2}$ - $N,K$ 为整数 - $|S|=N$ - $S$ 由 `A`、`B`、`C`、`?` 组成 ### 样例解释 1 将 `?` 替换为 `A`、`B`、`C` 后可能得到的字符串有 `AAAB`、`ABAB`、`ACAB` 共 $3$ 个。其中，`AAAB` 包含第 $1,2$ 个字符的 `AA` 以及第 $2,3$ 个字符的 `AA`，共 $2$ 个好字符串作为连续子串。注意，即使是相同的子串，只要在原字符串中的位置不同，也要分别计数。另一方面，`ABAB` 包含的好字符串只有 $1$ 个（`ABAB` 本身）。`ACAB` 也只包含 $1$ 个好字符串（`CAB`）。 ### 样例解释 2 请输出答案对 $998244353$ 取模后的结果。 由 ChatGPT 4.1 翻译