AT_arc171_f.[ARC171F] Both Reversible

当字符串 $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$ 取模的结果。

限制条件

• $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 翻译