406257: GYM102331 G Grammarly

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

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 one integer: the number of simple paths starting from $$$s$$$ in CauchySheep's graph, modulo $$$998\,244\,353$$$.

abba

13

benbeipo

255

iqiiiiiiqq

300

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

35