I samma anda som den virala hiten Pen-Pineapple-Apple-Pen (PPAP) av PIKOTARO ska du hitta antalet sätt att välja fyra icke-överlappande delsträngar från vänster till höger i den givna strängen $S = s_1 s_2 \ldots s_n$, som endast består av små engelska bokstäver, så att de fyra delsträngarna efterliknar den ikoniska PPAP-strukturen:
pen pineapple apple pen
Mer specifikt ska du välja åtta heltal $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$) sådana att:
- Den första och den fjärde delsträngen är identiska: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Detta representerar det matchande "pen" i början och slutet.
- Den tredje delsträngen är ett äkta suffix (strict suffix) till den andra delsträngen. Det vill säga, det finns ett heltal $k_2$ ($i_2 < k_2 \le j_2$) sådant att $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Detta fångar relationen mellan "pineapple" och "apple", där det senare är ett äkta suffix till det förra.
Du ska hitta antalet giltiga $8$-tupler $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ som uppfyller villkoren ovan.
Indata
Det finns bara ett testfall i varje testfil.
Den första och enda raden innehåller en sträng $S$ ($1 \le |S| \le 5 \times 10^3$) som anger den givna strängen bestående av endast små engelska bokstäver.
Utdata
Skriv ut en rad som innehåller ett heltal, vilket anger antalet giltiga val i PPAP-stil. Eftersom svaret kan vara stort, skriv ut det modulo $998\,244\,353$.
Exempel
ppaap
1
ppapppap
16
penpineappleapplepen
1502