PIKOTARO-ның әйгілі Pen-Pineapple-Apple-Pen (PPAP) вирустық хитінің рухында, тек кіші ағылшын әріптерінен тұратын берілген $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» сөзін білдіреді.
- Үшінші ішкі жол екінші ішкі жолдың қатаң жұрнағы (strict suffix) болып табылады. Яғни $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$ болатындай $k_2$ ($i_2 < k_2 \le j_2$) бүтін саны табылады. Бұл «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