W duchu wiralowego hitu Pen-Pineapple-Apple-Pen (PPAP) autorstwa PIKOTARO musisz znaleźć liczbę sposobów wyboru czterech nienachodzących na siebie podciągów spójnych (podsłów) od lewej do prawej w danym napisie $S = s_1 s_2 \ldots s_n$, składającym się wyłącznie z małych liter alfabetu angielskiego, tak aby te cztery podsłowa naśladowały kultową strukturę PPAP:
pen pineapple apple pen
Dokładniej mówiąc, należy wybrać osiem liczb całkowitych $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$) takich, że:
- Pierwsze i czwarte podsłowo są identyczne: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Odpowiada to pasującym słowom „pen” na początku i na końcu.
- Trzecie podsłowo jest właściwym sufiksem drugiego podsłowa. Oznacza to, że istnieje liczba całkowita $k_2$ ($i_2 < k_2 \le j_2$) taka, że $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Oddaje to zależność między „pineapple” oraz „apple”, gdzie drugie słowo jest właściwym sufiksem pierwszego.
Musisz wyznaczyć liczbę poprawnych $8$-krotek $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ spełniających powyższe warunki.
Wejście
W każdym pliku testowym znajduje się tylko jeden przypadek testowy.
Pierwszy i jedyny wiersz zawiera napis $S$ ($1 \le |S| \le 5 \times 10^3$) oznaczający dany napis składający się wyłącznie z małych liter alfabetu angielskiego.
Wyjście
Wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą liczbę poprawnych wyborów w stylu PPAP. Ponieważ odpowiedź może być duża, wypisz ją modulo $998\,244\,353$.
Przykład
ppaap
1
ppapppap
16
penpineappleapplepen
1502