题目描述

给定一个字符串 $s$，求由小写字符组成的，长度小于或等于 $s$ 的长度，字典序小于或等于 $s$，且为回文串的字符串 $t$ 的个数。

答案对 $998244353$ 取模。

输入格式

一行，一个字符串 $s$。

输出格式

一个整数表示答案。

aba

4

llll

620

数据范围

记 $n$ 为字符串长度。对于所有数据满足 $n≤5·10^6$。

本题共 $20$ 个测试点，从 $1$ 开始标号。若 $i$ 的二进制表示第 $j$ 位为 $1$，则数据 $i$ 满足性质 $j$ 。