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

样例

样例输入 1

ababa

样例输出 1

3

样例输入 2

?x?z

样例输出 2

703