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