Palindromic Substring

問題文

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

$S$ の空でない連続部分文字列 $S'$として考えられるもの全てについて以下の値を求め、それらの総和を答えてください。

• $S'$ の空でない連続部分文字列のうち、回文であるものの長さの総和

ただし、各連続部分文字列について、文字列として等しくても取り出した位置が異なるならば区別します。

また、答えは非常に大きくなることがあるので、答えを $998244353$ で割った余りを出力してください。

制約

• $1\leq N \leq 5×10^5$
• $S$ は英小文字からなる
• $N$ は整数

入力

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

出力

答えを出力してください。

入力例1

3
aba

出力例1

13

aba の空でない連続部分文字列は a、b、a、ab、ba、aba の $6$ つです。

a の空でない連続部分文字列のうち回文であるものは a の $1$ つで、長さの総和は $1$ です。
b の空でない連続部分文字列のうち回文であるものは b の $1$ つで、長さの総和は $1$ です。
a の空でない連続部分文字列のうち回文であるものは a の $1$ つで、長さの総和は $1$ です。
ab の空でない連続部分文字列のうち回文であるものは a、b の $2$ つで、長さの総和は $1+1=2$ です。
ba の空でない連続部分文字列のうち回文であるものは b、a の $2$ つで、長さの総和は $1+1=2$ です。
aba の空でない連続部分文字列のうち回文であるものは a、b、a、aba の $4$ つで、長さの総和は $1+1+1+3=6$ です。

以上より、答えは $1+1+1+2+2+6=13$ です。

入力例2

5
wakka

出力例2

55

入力例3

17
ushitapunichiakun

出力例3

969

ここにそのようなケースを置くことは出来ませんが、答えは非常に大きくなることがあるので $998244353$ で割った余りを出力することに注意してください。