AT_arc171_f [ARC171F] Both Reversible

[problemUrl]: https://atcoder.jp/contests/arc171/tasks/arc171_f 文字列 $ T $ が次の条件を満たす時、$ T $ を **良い文字列** と呼びます。 - 次の条件を全て満たす文字列の組 $ (A,\ B) $ が存在する。 - $ A,\ B $ はともに空でない。 - $ A\ +\ B\ =\ T $ - $ A\ +\ \mathrm{rev}(B) $ と $ \mathrm{rev}(A)\ +\ B $ はともに回文となる。 ここで $ A\ +\ B $ は文字列 $ A $ と文字列 $ B $ をこの順に結合してできる文字列を意味します。 また、$ \mathrm{rev}(A) $ は文字列 $ A $ の文字を逆順に並べ替えてできる文字列を意味します。 英小文字と `?` からなる長さ $ N $ の文字列 $ S $ があります。 $ S $ に含まれる `?` を英小文字に置き換える方法は $ 26^{(?\ の個数)} $ 通りありますが、そのうち置き換えた後の文字列が良い文字列になる方法は何通りありますか？答えを $ 998244353 $ で割った余りを求めてください。

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

問題文の条件を満たす置き換え方の個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 5\ \times\ 10^4 $ - $ S $ は英小文字と `?` からなる長さ $ N $ の文字列 ### Sample Explanation 1 文字列 `abab` は良い文字列です。なぜならば、$ A\ = $ `ab`, $ B\ = $ `ab` としたとき、$ A\ +\ B\ = $ `abab` であり $ A\ +\ \mathrm{rev}(B)\ = $ `abba` と $ \mathrm{rev}(A)\ +\ B\ = $ `baab` はともに回文となるからです。 $ S $ の `?` を英小文字に置き換えてできる文字列のうち、良い文字列は `abab` の $ 1 $ 通りのみです。