G. Grammarly
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

CauchySheep has a string $$$s$$$.

He looked at all its different non-empty substrings and added a directed edge from $$$a$$$ to $$$b$$$ if $$$|b|+1=|a|$$$ and $$$b$$$ is a substring of $$$a$$$.

You need to calculate the number of simple paths starting from $$$s$$$ in this graph, modulo $$$998\,244\,353$$$.

Input

The first line of the input contains a string $$$s$$$ consisting of lowercase Latin letters: the string CauchySheep has ($$$1 \leq |s| \leq 300\,000$$$).

Output

Output one integer: the number of simple paths starting from $$$s$$$ in CauchySheep's graph, modulo $$$998\,244\,353$$$.

Examples
Input
abba
Output
13
Input
benbeipo
Output
255
Input
iqiiiiiiqq
Output
300
Input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Output
35
Note