I ånden til den virale hiten Pen-Pineapple-Apple-Pen (PPAP) av PIKOTARO skal du finne antall måter å velge fire ikke-overlappende delstrenger fra venstre mot høyre i den gitte strengen $S = s_1 s_2 \ldots s_n$, som kun består av små engelske bokstaver, slik at de fire delstrengene etterligner den ikoniske PPAP-strukturen:
pen pineapple apple pen
Mer spesifikt skal du velge åtte heltall $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$) slik at:
- Den første og den fjerde delstrengen er identiske: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Dette representerer det matchende «pen» på begynnelsen og slutten.
- Den tredje delstrengen er et ekte suffiks (strict suffix) av den andre delstrengen. Det vil si at det finnes et heltall $k_2$ ($i_2 < k_2 \le j_2$) slik at $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Dette fanger opp forholdet mellom «pineapple» og «apple», der sistnevnte er et ekte suffiks av førstnevnte.
Du skal finne antall gyldige $8$-tupler $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ som oppfyller betingelsene ovenfor.
Inndata
Det er bare ett testtilfelle i hver testfil.
Den første og eneste linjen inneholder en streng $S$ ($1 \le |S| \le 5 \times 10^3$) som angir den gitte strengen bestående av kun små engelske bokstaver.
Utdata
Skriv ut én linje som inneholder ett heltall, som angir antall gyldige PPAP-lignende valg. Siden svaret kan være stort, skal det skrives ut modulo $998\,244\,353$.
Eksempler
ppaap
1
ppapppap
16
penpineappleapplepen
1502