Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

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

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#3312EditorialOpen题解:#14808. Pen Pineapple Apple PenDerRichterView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.