/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
英小文字からなる文字列 x が以下の条件を満たすとき，x をよい文字列と呼ぶことにします．
- x の長さ 2 以上の (連続する) 部分文字列は，すべて以下の条件を満たす．
- その部分文字列内で過半数を占める文字が存在しない．
例えば，acbca はよい文字列ではありません．
これは，部分文字列 cbc のなかで c が過半数を占めているからです．
英小文字と ? からなる長さ N の文字列 S が与えられます．
それぞれの ? を好きな英小文字に置き換ることで，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
Score : 400 points
Problem Statement
A string x consisting of lowercase English letters is said to be good if and only if the following condition is satisfied.
- Every (contiguous) substring of x whose length is 2 or greater satisfies the following:
- no character occupies the majority of that substring.
For example, acbca is not good because c occupies the majority of the substring cbc.
You are given a string S of length N consisting of lowercase English letters and ?.
You want to replace each ? with a lowercase English letter of your choice to make S a good string.
Find the number of ways to make S a good string, modulo 998244353.
Constraints
- 2 \leq N \leq 5000
- 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 answer.
Sample Input 1
3 a?b
Sample Output 1
24
Every way other than aab and abb satisfies the condition.
Sample Input 2
3 a?a
Sample Output 2
0
Sample Input 3
20 ugsyakganihodnwmktgi
Sample Output 3
1
Sample Input 4
20 ??a???h?m?y?ts???tl?
Sample Output 4
444225229