AT_pakencamp_2023_day3_a ABC

给定一个长度为 $N$ 的字符串 $S$。$S$ 的每个字符都是 $\mathtt{A}$、$\mathtt{B}$ 或 $\mathtt{C}$ 之一。 你将对 $S$ 进行如下操作 $K$ 次。请计算最终得到的 $S$ 作为可能的字符串数量，对 $998244353$ 取模后的结果。 - 选择 $1\leq i\leq |S|-1$ 的整数 $i$。如果 $S$ 的第 $i$ 个字符和第 $i+1$ 个字符相等，则在 $S$ 的第 $i$ 个字符之后插入一个与该字符相同的字符。否则，在 $S$ 的第 $i$ 个字符之后插入一个与 $S$ 的第 $i$ 个字符和第 $i+1$ 个字符都不同的字符（即在 $\mathtt{A}$、$\mathtt{B}$、$\mathtt{C}$ 中选择不同于这两个字符的字符）。

输入以如下格式给出。 > $N$ $K$ $S$

请输出最终可能得到的 $S$ 的字符串数量，对 $998244353$ 取模的结果。

### 样例解释 1 例如，可以按如下步骤构造 $\mathtt{AABCBB}$。 1. 令 $i=2$，在 $S$ 的第 2 个字符后插入 $\mathtt{C}$。 2. 令 $i=2$，在 $S$ 的第 2 个字符后插入 $\mathtt{B}$。 ### 数据范围 - $2\leq N\leq 2\times 10^5$ - $1\leq K\leq 2\times 10^5$ - $S$ 只包含 $\mathtt{A}$、$\mathtt{B}$、$\mathtt{C}$，长度为 $N$。 由 ChatGPT 5 翻译