AT_agc060_a [AGC060A] No Majority

当且仅当一个仅由小写英文字母组成的字符串 $x$ 满足以下条件时，我们称 $x$ 为**好**字符串。 - $x$ 的任意长度不少于 $2$ 的（连续）子串都满足以下条件： - 在该子串中不存在占据多数的字符。 例如，`acbca` 不是好字符串，因为其子串 `cbc` 中字符 `c` 占据了多数。 给定一个长度为 $N$ 的字符串 $S$，$S$ 由小写英文字母和 `?` 组成。你可以将每个 `?` 替换为任意小写英文字母。请问有多少种替换方式可以使 $S$ 成为好字符串？请将答案对 $998244353$ 取模后输出。

输入从标准输入中给出，格式如下： > $N$ $S$

请输出答案。

### 限制条件 - $2 \leq N \leq 5000$ - $S$ 是一个仅包含小写英文字母和 `?` 的长度为 $N$ 的字符串 ### 样例解释 1 除了 `aab` 和 `abb` 以外的所有方式都满足条件。 由 ChatGPT 4.1 翻译