分数: 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