Stronger Jovsi

Time limit1sMemory limit512 MB

Summary

Count the chains of palindromic substrings whose left ends strictly increase and right ends strictly decrease, modulo 998244353, for a string up to one million letters.

Level: Medium7 of 10
Topics: Dynamic programming, String matching, Prefix sum
Solved: No attempts yet

Problem

Jovsi is still a strong boy. Since childhood he loved machine guns and often imitated them, but for some reason he did not shout trtrtrt or bambambam. He shouted acacacacac.

Mr. Malnar is not impressed by Jovsi's strength. He is interested only in Jovsi's ability to solve problems. One day he gave Jovsi a stick with $n$ letters written from its left end to its right end.

Mr. Malnar finds symmetric sticks beautiful, so he is especially interested in palindrome pairs. A palindrome pair is an ordered pair of natural numbers $(l, r)$ with $1 \le l \le r \le n$ such that the word formed by the letters from position $l$ to position $r$ is a palindrome. A palindrome reads the same from left to right and from right to left.

Mr. Malnar then gives Jovsi a challenge. A challenge consists of a natural number $k$ and a sequence of $k$ palindrome pairs $(l_i, r_i)$ such that $l_1 < l_2 < \cdots < l_k$ and $r_1 > r_2 > \cdots > r_k$ .

Jovsi must be ready for any situation, so he wants to know how many different challenges he can receive from Mr. Malnar. Help Jovsi and print the number of different challenges modulo 998244353.

Input

The only line contains a word of lowercase English letters, the sequence of letters written on Mr. Malnar's stick. The word has at most one million characters.

Output

Print the number of different challenges modulo 998244353 on a single line.

Examples3

Example 1
Input
```
anadanaokoabanana
```
Expected output
```
65
```
Example 2
Input
```
acacacacac
```
Expected output
```
242
```
Example 3
Input
```
ananas
```
Expected output
```
18
```