Im Geiste des viralen Hits Pen-Pineapple-Apple-Pen (PPAP) von PIKOTARO musst du die Anzahl der Möglichkeiten bestimmen, in der gegebenen Zeichenkette $S = s_1 s_2 \ldots s_n$, die nur aus englischen Kleinbuchstaben besteht, von links nach rechts vier sich nicht überlappende Teilstrings auszuwählen, sodass die vier Teilstrings die ikonische PPAP-Struktur nachahmen:
pen pineapple apple pen
Genauer gesagt wählst du acht ganze Zahlen $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$), sodass gilt:
- Der erste und der vierte Teilstring sind identisch: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Dies steht für das übereinstimmende „pen“ am Anfang und am Ende.
- Der dritte Teilstring ist ein echtes Suffix des zweiten Teilstrings. Das heißt, es existiert eine ganze Zahl $k_2$ ($i_2 < k_2 \le j_2$), sodass $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$ gilt. Dies erfasst die Beziehung zwischen „pineapple“ und „apple“, wobei Letzteres ein echtes Suffix von Ersterem ist.
Du musst die Anzahl der gültigen $8$-Tupel $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ bestimmen, die die obigen Bedingungen erfüllen.
Eingabe
In jeder Testdatei gibt es nur einen einzigen Testfall.
Die erste und einzige Zeile enthält eine Zeichenkette $S$ ($1 \le |S| \le 5 \times 10^3$), die die gegebene Zeichenkette aus englischen Kleinbuchstaben angibt.
Ausgabe
Gib eine Zeile mit einer ganzen Zahl aus, die die Anzahl der gültigen Auswahlen im PPAP-Stil angibt. Da die Antwort groß sein kann, gib sie modulo $998\,244\,353$ aus.
Beispiele
ppaap
1
ppapppap
16
penpineappleapplepen
1502