题目描述

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

• $x$ 的每个（连续的）长度大于等于2的子串满足以下条件：
  • 该子串没有任何字符占据大多数。

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

给定一个长度为 $N$ 的由小写英文字母和 ? 组成的字符串 $S$，你需要用一个小写英文字母替换每个 ?，使得 $S$ 成为一个好的字符串。求将 $S$ 变为好字符串的方案数，取模 $998244353$。

约束条件

• $2 \\leq N \\leq 5000$
• $S$ 是一个长度为 $N$ 的由小写英文字母和 ? 组成的字符串。

输入

从标准输入中按以下格式给出输入：

$N$
$S$

输出

输出答案。

样例输入 1

3
a?b

样例输出 1

24

除了 aab 和 abb，其他方式都满足条件。

样例输入 2

3
a?a

样例输出 2

0

样例输入 3

20
ugsyakganihodnwmktgi

样例输出 3

1

样例输入 4

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

样例输出 4

444225229