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

You are given a string $S$ of length $n$. Initially, $T_0 = S$. In each step, you can delete the first or the last character of $T_i$ to obtain a new string $T_{i+1}$. After $n-1$ operations, we obtain a string $T_{n-1}$ consisting of a single character. Depending on the choices made at each step, there are $2^{n-1}$ possible sequences of operations. Note that even if deleting the first or last character results in the same string, we still treat them as two distinct operation sequences.

For a string $T$, let $occ(T)$ denote the number of occurrences of $T$ as a substring in $S$. For example, $occ(\textsf{aaa}, \textsf{aaabaaa}) = 3$.

For an operation sequence, its contribution is defined as $\prod_{i=1}^{n-1} occ(T_i)$. Calculate the sum of contributions over all possible operation sequences. Since the answer can be very large, output the result modulo $998\,244\,353$.

Input

A single line containing a string $S$. It is guaranteed that $S$ consists only of lowercase English letters.

Output

A single integer representing the answer.

Examples

Input 1

zzz

Output 1

24

Input 2

abbab

Output 2

53

Input 3

See the provided files.

Subtasks

There are 20 test cases in total.

For test cases 1–5, $|S| \leq 5\, 000$.

For test cases 6–8, each character of $S$ is generated independently and uniformly at random from a and b.

For test cases 9–14, $|S| \leq 6 \times 10^4$.

For all test cases, $1 \leq |S| \leq 10^5$.