分数: 400 点
问题陈述
一个字符串 x 由小写英文字母组成据说是 好 当且仅当满足以下条件时。
- 每个(连续)子串 x 其长度为 2 或更高版本满足以下条件:
- 没有字符占据该子字符串的大部分。
例如, acbca 不好,因为 c 占据子串的大部分 cbc.
给你一个字符串 S 长度 N 由小写英文字母和 ?。
你想替换每一个 ? 加上您选择的小写英文字母 S 一个好字符串。
找出制作方法的数量 S 一个好的字符串,模数 998244353.
约束
- 2 \leq N \leq 5000
- S 是一个长度为的字符串 N 由小写英文字母和
?.
输入
输入由标准输入按以下格式给出:
N S
输出
打印答案。
示例输入 1
3 a?b
示例输出 1
24
除了 aab 和 abb 满足条件。
示例输入 2
3 a?a
示例输出 2
0
示例输入 3
20 ugsyakganihodnwmktgi
示例输出 3
1
示例输入 4
20 ??a???h?m?y?ts???tl?
示例输出 4
444225229