Grammarly

Time limit2sMemory limit512 MB

Summary

Given a string up to 300,000 characters, count simple paths from the whole string through distinct substrings where each step deletes one character, modulo 998244353.

Level: Hard9 of 10
Topics: String, Dynamic programming, Trie
Solved: No attempts yet

Problem

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. Count the simple paths that start from s in this graph, modulo 998 244 353.

Input

The first line contains a string s of lowercase Latin letters ( $1 \le |s| \le 300\,000$ ).

Output

Print one integer: the number of simple paths starting from s, modulo 998 244 353.

Hint

Examples4

Example 1
Input
```
abba
```
Expected output
```
13
```
Example 2
Input
```
benbeipo
```
Expected output
```
255
```
Example 3
Input
```
iqiiiiiiqq
```
Expected output
```
300
```
Example 4
Input
```
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
```
Expected output
```
35
```