Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

In the spirit of the viral hit Pen-Pineapple-Apple-Pen (PPAP) by PIKOTARO, you need to find the number of ways to select four non-overlapping substrings from left to right in the given string $S = s_1 s_2 \ldots s_n$ consisting only of lowercase English letters, so that the four substrings mimic the iconic PPAP structure:

pen pineapple apple pen

More specifically, choosing eight integers $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$), such that:

  • The first and fourth substrings are identical: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. This represents the matching "pen" at the beginning and end.
  • The third substring is a strict suffix of the second substring. That is, there exists an integer $k_2$ ($i_2 < k_2 \le j_2$) such that $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. This captures the relationship between "pineapple" and "apple", where the latter is a strict suffix of the former.

You need to find the number of valid $8$-tuples $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ satisfying the above conditions.

Input

There is only one test case in each test file.

The first and only line contains a string $S$ ($1 \le |S| \le 5 \times 10^3$) indicating the given string consisting only of lowercase English letters.

Output

Output one line containing one integer, indicating the number of valid PPAP-style selections. As the answer might be large, output it modulo $998\,244\,353$.

Examples

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.