18923번 - Embeddings 다국어

Given a string $A$ of length $n$. Consider palindromic substrings of this string. Each palindromic substring is defined by its starting position $s$ and its end $e$ ($1 \le s \le e \le n$) such that letters in $A$ starting at position $s$ and ending at position $e$, inclusive, form a palindrome (i.e. $A[s+i]=A[e-i]$ for any integer $i$ between 0 and $e-s$, inclusive).

Let's define an embedding of depth $k \ge 1$ as a sequence of $k$ palindromic substrings of $A$ with the following property: $s_1 < \ldots < s_k$ and $e_1 > \ldots > e_k$, i.e. palindromes in the embedding are strictly contained in each other like the Russian dolls.

Given $A$, count the number of possible embeddings. Since this number can be too large, calculate it modulo $998\,244\,353$.

The input consists of a single line containing the string $A$. The string is non-empty and consists of no more than $10^6$ lowercase English letters.

Print the number of possible embeddings modulo $998\,244\,353$.

For the sample input 1, we have nine embeddings of depth 1 (1-1, 2-2, 3-3, 4-4, 5-5, 6-6, 2-4, 4-6, 1-5), six embeddings of depth 2 (3-3 in 2-4, 5-5 in 4-6, 2-2 in 1-5, 3-3 in 1-5, 4-4 in 1-5, 2-4 in 1-5), and one embedding of depth 3 (3-3 in 2-4 in 1-5), with $9+6+1=16$  embeddings in total.