В духе вирусного хита 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