P8351 [SDOI/SXOI2022] Substring Statistics

When Xiao D was four and a half years old, he learned the suffix automaton. You are given a string $S$ of length $n$. Initially, $T_0 = S$. Each time, you may delete a character from the beginning or the end of $T_i$ to obtain a new string $T_{i+1}$. After $n - 1$ operations, we will obtain a string $T_{n-1}$ with only one character. Depending on the choice of deletion each time, there are a total of $2^{n-1}$ possible operation sequences. Note that although for some operation, deleting the first character or the last character may produce the same string, we still treat them as two different operation sequences. For a string $T$, let $\operatorname{\textit{occ}}(T)$ denote the number of times $T$ occurs in $S$ as a substring. For example, $\operatorname{\textit{occ}}(\texttt{aaa},\texttt{aaaabaaa}) = 3$. For an operation sequence, define its contribution as $$\prod_{i = 1}^{n - 1} \operatorname{\textit{occ}}(T_i)$$ Compute the sum of contributions over all operation sequences. Since the answer can be very large, output the result modulo $998244353$.

A single line containing a string $S$, guaranteed to consist only of lowercase letters.

Output one line containing an integer representing the answer.

### Constraints This problem has $20$ test points. - For test points $1 \sim 5$, $|S| \le 5000$. - For test points $6 \sim 8$, each character of $S$ is generated independently and uniformly at random from $\texttt a$ and $\texttt b$. - For test points $9 \sim 14$, $|S| \le 6 \times 10^4$. For all testdata, $1 \le |S| \le 10^5$. $S$ contains only lowercase English letters. Translated by ChatGPT 5