Problem Description

Given a string $S$ that contains only lowercase letters.
Find the number of ways to partition $S$ into several non-overlapping palindromic substrings, modulo $998244353$.

Below is the formal statement.

Please compute the number of ways (with no limit on the count) to choose some intervals $[L_1,R_1],[L_2,R_2],\cdots,[L_m,R_m]$ such that the following conditions are satisfied, modulo $998244353$:

• $L_1=1$, $R_m=|S|$.
• For all $i\in[1,m]$, $L_i\le R_i$.
• For all $i\in[1,m)$, $R_i+1=L_{i+1}$.
• For all $i\in[1,m]$, the string $S_{L_i}S_{L_i+1}\cdots S_{R_i}$ is a palindrome (indices start from $1$).

Input Format

One line: the string $S$.

Output Format

One line: the number of valid ways modulo $998244353$.

abbba

5

aabcccbaa

22

abcbabcacabbcbabbcabbbcbabcbabcbcaacaaa

217952

Hint

• For $100\%$ of the testdata, $1\le |S|\le10^6$, and $S$ contains only lowercase letters.

Translated by ChatGPT 5