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.

제한

힌트