← 返回题目列表

AtCoder · arc171_f

F. 均可逆

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

一个字符串 T 被称为 好字符串 当满足以下条件时:

  • 有一对字符串 (A, B) 满足以下所有条件:
    • 两者 A 和 B 非空。
    • A + B = T.
    • 两者 A + \mathrm{rev}(B) 和 \mathrm{rev}(A) + B 是回文。

在这里, A + B 表示字符串连接而成的字符串 A 和 B 按此顺序。
另外, \mathrm{rev}(A) 表示将string中的字符顺序颠倒后形成的字符串 A.

有一个字符串 S 长度 N 由小写英文字母和字符组成 ?.
其中 26^{(\text{number of ?s})} 更换方法 ?s 在 S 包含小写英文字母,有多少个结果是一个好的字符串?求计数模数 998244353.

约束

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

输入

输入由标准输入按以下格式给出:

N
S

输出

打印数字,模数 998244353,替换问题陈述中满足条件的字符的方法。


示例输入 1

4
?ba?

示例输出 1

1

字符串 abab 很好,因为如果我们设置 A = ab 和 B = ab,那么 A + B = abab,以及两者 A + \mathrm{rev}(B) = abba 和 \mathrm{rev}(A) + B = baab 是回文。
通过替换可以形成的字符串中 ?s 在 S 是小写英文字母,好的字符串只有一个,就是 abab.


示例输入 2

10
?y?x?x????

示例输出 2

676

示例输入 3

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

示例输出 3

193994800

示例输入 4

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

示例输出 4

363594614