У дусі вірусного хіта Pen-Pineapple-Apple-Pen (PPAP) виконавця PIKOTARO вам потрібно знайти кількість способів вибрати чотири неперетинні підрядки зліва направо в заданому рядку $S = s_1 s_2 \ldots s_n$, що складається лише з малих англійських літер, так, щоб ці чотири підрядки імітували культову структуру PPAP:
pen pineapple apple pen
Точніше кажучи, потрібно вибрати вісім цілих чисел $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_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Це відповідає однаковому слову «pen» на початку та в кінці.
- Третій підрядок є строгим суфіксом другого підрядка. Тобто існує ціле число $k_2$ ($i_2 < k_2 \le j_2$) таке, що $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Це відображає зв'язок між «pineapple» та «apple», де друге слово є строгим суфіксом першого.
Вам потрібно знайти кількість коректних кортежів із $8$ чисел $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$, що задовольняють наведені вище умови.
Вхідні дані
У кожному тестовому файлі міститься лише один набір вхідних даних.
Перший і єдиний рядок містить рядок $S$ ($1 \le |S| \le 5 \times 10^3$), що позначає заданий рядок, який складається лише з малих англійських літер.
Вихідні дані
Виведіть один рядок, що містить одне ціле число — кількість коректних виборів у стилі PPAP. Оскільки відповідь може бути великою, виведіть її за модулем $998\,244\,353$.
Приклади
ppaap
1
ppapppap
16
penpineappleapplepen
1502