题目描述

当且仅当一个仅由小写英文字母组成的字符串 $x$ 满足以下条件时，我们称 $x$ 为好字符串。

• $x$ 的任意长度不少于 $2$ 的（连续）子串都满足以下条件：
  • 在该子串中不存在占据多数的字符。

例如，acbca 不是好字符串，因为其子串 cbc 中字符 c 占据了多数。

给定一个长度为 $N$ 的字符串 $S$，$S$ 由小写英文字母和 ? 组成。你可以将每个 ? 替换为任意小写英文字母。请问有多少种替换方式可以使 $S$ 成为好字符串？请将答案对 $998244353$ 取模后输出。

输入格式

输入从标准输入中给出，格式如下：

$N$ $S$

输出格式

请输出答案。

样例 1

输入

3
a?b

输出

24

样例 2

输入

3
a?a

输出

0

样例 3

输入

20
ugsyakganihodnwmktgi

输出

1

样例 4

输入

20
??a???h?m?y?ts???tl?

输出

444225229

说明/提示

限制条件

• $2 \leq N \leq 5000$
• $S$ 是一个仅包含小写英文字母和 ? 的长度为 $N$ 的字符串

样例解释 1

除了 aab 和 abb 以外的所有方式都满足条件。

由 ChatGPT 4.1 翻译