18474번 - 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 ≤ |s| ≤ 300 000).

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