题目描述

给定一个只包含小写字母的字符串 $S$。
求出将 $S$ 划分成若干个互不相交的回文子串的方案数对 $998244353$ 取模的结果。

下面是形式题面。

请计算出选择一些区间（数量不限） $[L_1,R_1],[L_2,R_2],\cdots,[L_m,R_m]$ 满足以下条件的方案数对 $998244353$ 取模的结果：

• $L_1=1$，$R_m=|S|$。
• $\forall i\in[1,m]$，$L_i\le R_i$。
• $\forall i\in[1,m)$，$R_i+1=L_{i+1}$。
• $\forall i\in[1,m]$，字符串 $S_{L_i}S_{L_i+1}\cdots S_{R_i}$ 是回文串（下标从 $1$ 开始）。

输入格式

一行，为字符串 $S$。

输出格式

一行，为方案数对 $998244353$ 取模后的结果。

abbba

5

aabcccbaa

22

abcbabcacabbcbabbcabbbcbabcbabcbcaacaaa

217952

提示

• 对于 $100\%$ 的数据，有 $1\le |S|\le10^6$，$S$ 中仅包含小写字母。