配点 : $400$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$

$S$

出力

答えを出力せよ．

3
a?b

24

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

3
a?a

0

20
ugsyakganihodnwmktgi

1

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

444225229