ピコ太郎の大ヒット曲「ペンパイナッポーアッポーペン(PPAP)」の精神に則り、英小文字のみからなる与えられた文字列 $S = s_1 s_2 \ldots s_n$ から、左から右へ互いに重ならない 4 つの部分文字列を選ぶ方法のうち、それら 4 つの部分文字列が象徴的な PPAP の構造を模倣するようなものの個数を求めてください。
pen pineapple apple pen
より具体的には、次の条件を満たす 8 つの整数 $i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4$($1 \le i_1 \le j_1 < i_2 \le j_2 < i_3 \le j_3 < i_4 \le j_4 \le n$)を選びます。
- 1 番目と 4 番目の部分文字列が一致する:$s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$。これは先頭と末尾で一致する「pen」を表します。
- 3 番目の部分文字列が 2 番目の部分文字列の真の接尾辞(strict suffix)である。すなわち、ある整数 $k_2$($i_2 < k_2 \le j_2$)が存在して $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$ を満たす。これは後者が前者の真の接尾辞であるという「pineapple」と「apple」の関係を表します。
上記の条件を満たす有効な $8$ つ組 $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ の個数を求めてください。
入力
各テストファイルには 1 つのテストケースのみが含まれます。
唯一の行には、英小文字のみからなる与えられた文字列を表す文字列 $S$($1 \le |S| \le 5 \times 10^3$)が与えられます。
出力
有効な PPAP 型の選び方の個数を表す 1 つの整数を 1 行に出力してください。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。
入出力例
ppaap
1
ppapppap
16
penpineappleapplepen
1502