P14185 Counting Palindromic Substring Partitions

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$).

One line: the string $S$.

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

- For $100\%$ of the testdata, $1\le |S|\le10^6$, and $S$ contains only lowercase letters. Translated by ChatGPT 5