AT_agc060_a [AGC060A] No Majority

[problemUrl]: https://atcoder.jp/contests/agc060/tasks/agc060_a 英小文字からなる文字列 $ x $ が以下の条件を満たすとき，$ x $ を**よい**文字列と呼ぶことにします． - $ x $ の長さ $ 2 $ 以上の (連続する) 部分文字列は，すべて以下の条件を満たす． - その部分文字列内で過半数を占める文字が存在しない． 例えば，`acbca` はよい文字列ではありません． これは，部分文字列 `cbc` のなかで `c` が過半数を占めているからです． 英小文字と `?` からなる長さ $ N $ の文字列 $ S $ が与えられます． それぞれの `?` を好きな英小文字に置き換ることで，$ S $ をよい文字列にしたいです． $ S $ をよい文字列にする方法が何通りあるかを $ 998244353 $ で割ったあまりを求めてください．

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

答えを出力せよ．

### 制約 - $ 2\ \leq\ N\ \leq\ 5000 $ - $ S $ は英小文字と `?` からなる長さ $ N $ の文字列 ### Sample Explanation 1 `aab`, `abb` 以外の方法が条件を満たします．