题目描述

当字符串 $T$ 满足以下条件时，称 $T$ 为好字符串。

• 存在一组字符串 $(A, B)$，满足以下所有条件：
  • $A$ 和 $B$ 都非空。
  • $A + B = T$。
  • $A + \mathrm{rev}(B)$ 和 $\mathrm{rev}(A) + B$ 都是回文串。

这里，$A + B$ 表示将字符串 $A$ 和字符串 $B$ 按顺序连接得到的新字符串。
此外，$\mathrm{rev}(A)$ 表示将字符串 $A$ 的字符顺序反转得到的新字符串。

给定一个由小写英文字母和 ? 组成、长度为 $N$ 的字符串 $S$。
将 $S$ 中的每个 ? 替换为小写英文字母的方法共有 $26^{(\text{? 的个数})}$ 种，其中有多少种替换后得到的字符串是好字符串？请输出方案数对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $S$

输出格式

请输出满足题意的替换方案数对 $998244353$ 取模的结果。

样例 1

输入

4
?ba?

输出

1

样例 2

输入

10
?y?x?x????

输出

676

样例 3

输入

30
???a?????aab?a???c????c?aab???

输出

193994800

样例 4

输入

36
????????????????????????????????????

输出

363594614

说明/提示

限制条件

• $2 \leq N \leq 5 \times 10^4$
• $S$ 是由小写英文字母和 ? 组成的长度为 $N$ 的字符串

样例解释 1

字符串 abab 是好字符串。因为当 $A =$ ab，$B =$ ab 时，$A + B =$ abab，且 $A + \mathrm{rev}(B) =$ abba 和 $\mathrm{rev}(A) + B =$ baab 都是回文串。因此，$S$ 中 ? 替换后能得到好字符串的方案只有 abab 这一种。

由 ChatGPT 4.1 翻译