Problem Description

Little D learned suffix automata when he was four and a half years old.

You have a string \( S \) with length \( n \). Initially, \( T_0 = S \). Each time, you can remove a character from the beginning or the end of \( T_i \) to get a new string \( T_{i+1} \). After \( n-1 \) operations, we will end up with a string \( T_{n-1} \) that consists of only one character. There are \( 2^{n-1} \) possible sequences of operations due to the choices made at each step. Note that even if an operation to remove a character from the beginning or the end results in the same string, we still consider them as two different sequences.

For a string \( T \), we denote \( \operatorname{occ}(T) \) as the number of times \( T \) appears as a substring in \( S \). For example, \( \operatorname{occ}(\texttt{aaa}, \texttt{aaaabaaa}) = 3 \).

For a sequence of operations, its contribution is defined as:

\[ \prod_{i=1}^{n-1} \operatorname{occ}(T_i) \]

Calculate the sum of contributions for all possible sequences of operations. Since the answer can be very large, output the result modulo \( 998244353 \).

Input Format

There is only one line containing the string \( S \), which consists of lowercase letters.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

zzz

Sample Output #1

24

Sample Input #2

abbab

Sample Output #2

53

Sample Input #3

See the attached sample file ex_substring3.in

Sample Output #3

See the attached sample file ex_substring3.out

Notes

Data Size and Constraints

There are 20 test cases in total.

• For test cases 1 to 5, \( |S| \leq 5000 \).
• For test cases 6 to 8, each character of \( S \) is independently and equally likely to be 'a' or 'b'.
• For test cases 9 to 14, \( |S| \leq 6 \times 10^4 \).

For all test cases, \( 1 \leq |S| \leq 10^5 \). \( S \) consists of only lowercase English letters.

见题面 Input 部分

见题面 Output 部分