PIKOTAROn viraalihitin Pen-Pineapple-Apple-Pen (PPAP) hengessä tehtäväsi on laskea, kuinka monella tavalla annetusta vain pieniä englantilaisia kirjaimia sisältävästä merkkijonosta $S = s_1 s_2 \ldots s_n$ voidaan valita vasemmalta oikealle neljä toisiaan leikkaamatonta osamerkkijonoa siten, että nämä neljä osamerkkijonoa jäljittelevät ikonista PPAP-rakennetta:
pen pineapple apple pen
Tarkemmin sanottuna valitaan kahdeksan kokonaislukua $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$) siten, että:
- Ensimmäinen ja neljäs osamerkkijono ovat samat: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Tämä vastaa alussa ja lopussa täsmäävää sanaa "pen".
- Kolmas osamerkkijono on toisen osamerkkijonon aito loppuosa (strict suffix). Toisin sanoen on olemassa sellainen kokonaisluku $k_2$ ($i_2 < k_2 \le j_2$), että $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Tämä kuvaa sanojen "pineapple" ja "apple" välistä suhdetta, jossa jälkimmäinen on edellisen aito loppuosa.
Tehtäväsi on löytää edellä mainitut ehdot täyttävien kelvollisten $8$-monikkojen $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ lukumäärä.
Syöte
Jokaisessa testitiedostossa on vain yksi testitapaus.
Ensimmäinen ja ainoa rivi sisältää merkkijonon $S$ ($1 \le |S| \le 5 \times 10^3$), joka koostuu vain pienistä englantilaisista kirjaimista.
Tuloste
Tulosta yksi rivi, joka sisältää yhden kokonaisluvun: kelvollisten PPAP-tyylisten valintojen lukumäärän. Koska vastaus voi olla suuri, tulosta se modulo $998\,244\,353$.
Esimerkit
ppaap
1
ppapppap
16
penpineappleapplepen
1502