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