問題文

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

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

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

英小文字と ? からなる長さ $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