题目描述

英小文字からなる文字列 $x$ が以下の条件を満たすとき，$x$ をよい文字列と呼ぶことにします．

• $x$ の長さ $2$ 以上の (連続する) 部分文字列は，すべて以下の条件を満たす．
  • その部分文字列内で過半数を占める文字が存在しない．

例えば，acbca はよい文字列ではありません． これは，部分文字列 cbc のなかで c が過半数を占めているからです．

英小文字と ? からなる長さ $N$ の文字列 $S$ が与えられます． それぞれの ? を好きな英小文字に置き換ることで，$S$ をよい文字列にしたいです． $S$ をよい文字列にする方法が何通りあるかを $998244353$ で割ったあまりを求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $S$

输出格式

答えを出力せよ．

题目大意

给你一个由小写英文与问号组成的字符串，问号可以用任意一个小写英文字母替换，请你计算有多少种替换方法，可以使这个字符串成为好的字符串，答案模 $998244353$ 。

一个好的字符串 $x$ 满足如下条件：

对于 $x$ 的每一个长度大于等于 $2$ 的连续子串，都没有某一种字符的数量大于字串长度的一半。

3
a?b

24

3
a?a

0

20
ugsyakganihodnwmktgi

1

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

444225229

提示

制約

• $2\ \leq\ N\ \leq\ 5000$
• $S$ は英小文字と ? からなる長さ $N$ の文字列

Sample Explanation 1

aab, abb 以外の方法が条件を満たします．