避开 K 回文

题目描述

给定一个长度为 $N$,由字符 A、B、? 组成的字符串 $S$。另给定一个正整数 $K$。

由 A 和 B 组成的字符串 $T$ 被称为「好字符串」,当且仅当它满足以下条件:

• $T$ 中不存在长度为 $K$ 的连续子串是回文。

设 $S$ 中 ? 的个数为 $q$。把 $S$ 中的每个 ? 替换成 A 或 B,共可以得到 $2^q$ 个字符串。求其中有多少个是好字符串。

答案可能很大,请对 $998244353$ 取模后输出。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$S$

输出格式

输出答案。

样例

7 4
AB?A?BA

1

该字符串有两个 ?。把每个 ? 替换成 A 或 B,共得到 4 个字符串:

ABAAABA

ABAABBA

ABBAABA

ABBABBA

其中,后三个包含长度为 4 的回文连续子串 ABBA,因此不是好字符串。

所以应输出 1。

40 7
????????????????????????????????????????

116295436

请注意对 $998244353$ 取模后输出好字符串的个数。

15 5
ABABA??????????

0

有可能不存在任何替换方案,使得得到的字符串是好字符串。

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

259240

数据范围

• $2 \le K \le N \le 1000$
• $K \le 10$
• $S$ 是由 A、B、? 组成的字符串。
• $S$ 的长度为 $N$。
• $N$、$K$ 均为整数。