分数: 450 点
问题陈述
给你一个字符串 S 长度 N 由字符组成 A, B,和 ?.
还给你一个正整数 K。
一个字符串 T 组成 A 和 B 被认为是 好字符串 如果满足以下条件:
- No 长度连续的子串 K in T 是一个回文。
让 q 是数量 ? 中的字符 S。
有 2^q 可以通过替换每个字符串来获得 ? in S 与任一 A or B。找出这些字符串中有多少是好字符串。
计数可能非常大,因此求模 998244353.
约束
- 2 \leq K \leq N \leq 1000
- K \leq 10
- S 是一个由以下组成的字符串
A,B,和?. - 的长度 S is N.
- N 和 K 是整数。
输入
输入由标准输入按以下格式给出:
N K S
输出
打印答案。
示例输入 1
7 4 AB?A?BA
示例输出 1
1
给定的字符串有两个 ?s。
分别替换得到四个字符串 ? 与 A or B:
ABAAABAABAABBAABBAABAABBABBA
其中,最后三个包含连续的子字符串 ABBA 的长度为 4,这是一个回文,因此不是好的字符串。
因此,您应该打印 1.
示例输入 2
40 7 ????????????????????????????????????????
示例输出 2
116295436
确保找到好字符串的模数 998244353.
示例输入 3
15 5 ABABA??????????
示例输出 3
0
可能没有办法更换 ?s 获得一个好的字符串。
示例输入 4
40 8 ?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA
示例输出 4
259240