시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 4 4 80.000%

문제

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.

예제 입력 1

abba

예제 출력 1

13

예제 입력 2

benbeipo

예제 출력 2

255

예제 입력 3

iqiiiiiiqq

예제 출력 3

300

예제 입력 4

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

예제 출력 4

35

힌트