Palindrome Factorization

問題文

長さ $N$ の英小文字 (a-z) からなる文字列 $S$ が与えられます。

$S$ の隣り合う文字の間にある $N - 1$ 箇所それぞれについて、仕切りを入れるか入れないか選び、$S$ を $1$ 個以上の空でない文字列に分割します。

分割して得られる文字列がすべて回文であるとき、その仕切りの入れ方を 良い入れ方 と呼びます。

良い入れ方 の総数を $998244353$ で割った余りを求めてください。

制約

• $N$ は整数
• $1 \leq N \leq 5 \times 10^5$
• $S$ は英小文字 (a-z) からなる長さ $N$ の文字列

入力

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

出力

$1$ 行に答えを出力せよ。

サンプル 1

入力

3
aba

出力

2

aba と a|b|a の $2$ 通りです。

サンプル 2

入力

4
aaaa

出力

8

どのように仕切りを入れても、分割して得られる文字列はすべて回文です。

サンプル 3

入力

7
abacaba

出力

7

例えば、a|bacab|a は良い入れ方です。