P16017 [ICPC 2021 NAC] Ketek Counting

定义一个 *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$ 取模的结果。

翻译由 DeepSeek V3.2 完成