Problem Description

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$.

Input Format

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

Output Format

Output one line containing an integer representing the answer.

zzz

24

abbab

53

见附加样例文件中的 ex_substring3.in

见附加样例文件中的 ex_substring3.out

Hint

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