Siguiendo el espíritu del éxito viral Pen-Pineapple-Apple-Pen (PPAP) de PIKOTARO, debes encontrar el número de formas de seleccionar cuatro subcadenas que no se solapen de izquierda a derecha en la cadena dada $S = s_1 s_2 \ldots s_n$, formada únicamente por letras minúsculas del alfabeto inglés, de modo que las cuatro subcadenas imiten la icónica estructura de PPAP:
pen pineapple apple pen
Más específicamente, se trata de elegir ocho enteros $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$), tales que:
- La primera y la cuarta subcadena sean idénticas: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Esto representa el "pen" coincidente al principio y al final.
- La tercera subcadena sea un sufijo estricto de la segunda subcadena. Es decir, existe un entero $k_2$ ($i_2 < k_2 \le j_2$) tal que $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Esto captura la relación entre "pineapple" y "apple", donde la segunda es un sufijo estricto de la primera.
Debes hallar el número de $8$-tuplas válidas $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ que satisfacen las condiciones anteriores.
Entrada
Solo hay un caso de prueba en cada archivo de prueba.
La primera y única línea contiene una cadena $S$ ($1 \le |S| \le 5 \times 10^3$) que indica la cadena dada formada únicamente por letras minúsculas del alfabeto inglés.
Salida
Imprime una línea con un entero, indicando el número de selecciones válidas al estilo PPAP. Como la respuesta puede ser grande, imprímela módulo $998\,244\,353$.
Ejemplos
ppaap
1
ppapppap
16
penpineappleapplepen
1502