Í anda vinsæla smellsins Pen-Pineapple-Apple-Pen (PPAP) eftir PIKOTARO þarftu að finna fjölda leiða til að velja fjóra hlutstrengi sem skarast ekki frá vinstri til hægri í gefna strengnum $S = s_1 s_2 \ldots s_n$, sem samanstendur eingöngu af enskum lágstöfum, þannig að hlutstrengirnir fjórir líki eftir hinni þekktu PPAP-uppbyggingu:
pen pineapple apple pen
Nánar tiltekið þarf að velja átta heiltölur $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$) þannig að:
- Fyrsti og fjórði hlutstrengurinn eru eins: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Þetta táknar „pen“ í upphafi og enda sem passa saman.
- Þriðji hlutstrengurinn er eiginleg ending (strict suffix) annars hlutstrengsins. Það er að segja, til er heiltala $k_2$ ($i_2 < k_2 \le j_2$) þannig að $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Þetta fangar sambandið á milli „pineapple“ og „apple“, þar sem síðara orðið er eiginleg ending þess fyrra.
Þú þarft að finna fjölda gildra $8$-unda $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ sem uppfylla skilyrðin hér að ofan.
Inntak
Það er aðeins eitt prófunartilvik í hverri prófunarskrá.
Fyrsta og eina línan inniheldur streng $S$ ($1 \le |S| \le 5 \times 10^3$) sem táknar gefna strenginn sem samanstendur eingöngu af enskum lágstöfum.
Úttak
Prentið eina línu sem inniheldur eina heiltölu sem táknar fjölda gildra valmöguleika í PPAP-stíl. Þar sem svarið getur verið stórt skal prenta það modulo $998\,244\,353$.
Dæmi
ppaap
1
ppapppap
16
penpineappleapplepen
1502