Score: $1100$ points

问题陈述

当一个字符串 $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{number of ?s})}$ 种方式中，有多少种会得到一个好字符串？找出这个计数，并对 $998244353$ 取模。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

A string $T$ is called a good string when it satisfies the following condition:

• There is a pair of strings $(A, B)$ that satisfies all of the following:
  • Both $A$ and $B$ are non-empty.
  • $A + B = T$.
  • Both $A + \mathrm{rev}(B)$ and $\mathrm{rev}(A) + B$ are palindromes.

Here, $A + B$ denotes the string formed by concatenating strings $A$ and $B$ in this order.
Also, $\mathrm{rev}(A)$ denotes the string formed by reversing the order of the characters in string $A$.

There is a string $S$ of length $N$ consisting of lowercase English letters and the character ?.
Among the $26^{(\text{number of ?s})}$ ways to replace the ?s in $S$ with lowercase English letters, how many result in a good string? Find the count modulo $998244353$.

Constraints

• $2 \leq N \leq 5 \times 10^4$
• $S$ is a string of length $N$ consisting of lowercase English letters and ?.

Input

The input is given from Standard Input in the following format:

$N$

$S$

Output

Print the number, modulo $998244353$, of ways to replace the characters that satisfy the condition in the problem statement.

Sample Input 1

4
?ba?

Sample Output 1

1

The string abab is good, because if we set $A =$ ab and $B =$ ab, then $A + B =$ abab, and both $A + \mathrm{rev}(B) =$ abba and $\mathrm{rev}(A) + B =$ baab are palindromes.
Among the strings that can be formed by replacing the ?s in $S$ with lowercase English letters, there is only one good string, which is abab.

Sample Input 2

10
?y?x?x????

Sample Output 2

676

Sample Input 3

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

Sample Output 3

193994800

Sample Input 4

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

Sample Output 4

363594614