题目描述

定义一个 Ketek 为一个在单词级别上正反读起来相同的句子。例如，“fall leaves after leaves fall” 就是一个 Ketek，因为其单词顺序反转后与原顺序相同。

给定一个由小写字母和字符 ‘?’ 组成的字符串，请计算通过以下操作可以得到的本质不同的 Ketek 的数量：将每个 ‘?’ 替换为一个小写字母（每个 ‘?’ 替换成一个字母），并可以在任意字母之间选择性地添加空格。注意，Ketek 中不能包含任何 ‘?’；所有 ‘?’ 必须全部替换为小写字母。

例如，若初始字符串为 “ababa”，则可以构成 3 个不同的 Ketek：“ababa”、“a bab a” 和 “a b a b a”。

若初始字符串为 “?x?z”，则可以构成 703 个不同的 Ketek：

• 共有 $26^2 = 676$ 种方式替换 ‘?’，从而形成一个单词的 Ketek。
• 添加空格形成 “? x? z”。有 26 种方式构成 Ketek（第一个 ‘?’ 必须是 z；另一个 ‘?’ 可以是任意小写字母）。
• 添加空格形成 “?x ?z”。无法构成 Ketek。
• 添加空格形成 “? x ? z”。有 1 种方式构成 Ketek（第一个 ‘?’ 必须是 z；第二个 ‘?’ 必须是 x）。

总计 $676 + 26 + 0 + 1 = 703$。

两个 Ketek 被认为是不同的，如果它们包含的单词数量不同，或者在某一个单词索引处对应的单词不相同。

输入格式

输入只有一行，包含一个字符串 $s$（$1 \le |s| \le 30{,}000$），该字符串由小写字母（‘a’–‘z’）和字符 ‘?’ 组成。

输出格式

输出通过替换 ‘?’ 为小写字母并添加空格可以构成的本质不同的 Ketek 的数量。由于这个数字可能很大，请输出其对 $998{,}244{,}353$ 取模的结果。

ababa

3

?x?z 

703

提示

翻译由 DeepSeek V3.2 完成