問題文

文字列 S に対して、以下の条件を満たす長さ 1 以上の文字列 A, B が存在するとき、S は「ゴママヨである」と言います。

• S は A と B をこの順に結合した文字列に等しく、 A の最後の文字と B の最初の文字が等しい。

例えば、文字列 abba や abbcddc はゴママヨですが、 ababa はゴママヨではありません。

英小文字からなる文字列 S が与えられます。(i, j) (1 \leq i \leq j \leq |S|) であって、 S の i 文字目から j 文字目までを取り出した連続部分文字列がゴママヨであるようなものの個数を 998244353 で割った余り求めてください。

制約

• 1 \leq |S| \leq 10^{6}
• S は英小文字からなる文字列

入力例 1

abbcc

出力例 1

8

bb, cc, abb, bbc, bcc, abbc, bbcc, abbcc はゴママヨなので、 (2, 3), (4, 5), (1, 3), (2, 4), (3, 5), (1, 4), (2, 5), (1, 5) は条件を満たします。 これら以外の (i,j) は条件を満たしません。

入力例 2

ssss

出力例 2

6

入力例 3

kotamanegi

出力例 3

0