String Deletion Sequence Contribution Sum

You are given a string S of length n. Initially, we define T₀ = S. In each step, you can remove either the first or the last character of the current string T_i to obtain a new string T_i+1. After exactly n−1 operations, the string reduces to a single character T_n−1. Note that even if removing the first or the last character results in the same string, they are considered as two different operation sequences. Hence, there are a total of 2ⁿ⁻¹ operation sequences.

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

For an operation sequence, its contribution is defined as:

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

Your task is to compute the sum of contributions of all possible operation sequences modulo 998244353.

Note: Even though a removal operation may produce a string that has appeared before (or that could be produced by a different removal), each sequence is counted separately.

inputFormat

The input consists of a single line containing the string S.

Constraints: It is guaranteed that the length of S is at least 1. (For the purpose of this problem, you may assume that n is sufficiently small so that an \(O(n^2)\) solution is acceptable.)

outputFormat

Output one integer: the sum of contributions of all operation sequences modulo 998244353.

sample

a

1