题目详情
返回题库题目描述
给你一个长度为N的字符串S，由字符A、B和?组成。
同时给你一个正整数K。如果满足以下条件，由A和B组成的字符串T将被视为好字符串：
- 在T中，没有长度为K的连续子串是回文字符串。
设q是S中的?的数量。如果把?替换为A或B`，可以得到$2_q$个字符串。请找出其中有多少个字符串是好字符串。
这个数目可能非常大，所以求出它的模数998244353。
输入描述
第一行N和K
第二行字符串S
数据范围：
- 2≤K≤N≤1000
- K≤10
字符串S中只包含A,B, and?.- 字符串S的长度为N
输出描述
打印答案