Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

У дусі вірусного хіта 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

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.