103593: [Atcoder]ABC359 D - Avoid K Palindrome

Problem Statement

You are given a string $S$ of length $N$ consisting of characters A, B, and ?.

You are also given a positive integer $K$. A string $T$ consisting of A and B is considered a good string if it satisfies the following condition:

• No contiguous substring of length $K$ in $T$ is a palindrome.

Let $q$ be the number of ? characters in $S$. There are $2^q$ strings that can be obtained by replacing each ? in $S$ with either A or B. Find how many of these strings are good strings.

The count can be very large, so find it modulo $998244353$.

Constraints

• $2 \leq K \leq N \leq 1000$
• $K \leq 10$
• $S$ is a string consisting of A, B, and ?.
• The length of $S$ is $N$.
• $N$ and $K$ are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$S$

Output

Print the answer.

Sample Input 1

7 4
AB?A?BA

Sample Output 1

1

The given string has two ?s. There are four strings obtained by replacing each ? with A or B:

• ABAAABA
• ABAABBA
• ABBAABA
• ABBABBA

Among these, the last three contain the contiguous substring ABBA of length 4, which is a palindrome, and thus are not good strings.

Therefore, you should print 1.

Sample Input 2

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

Sample Output 2

116295436

Ensure to find the number of good strings modulo $998244353$.

Sample Input 3

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

Sample Output 3

0

It is possible that there is no way to replace the ?s to obtain a good string.

Sample Input 4

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

Sample Output 4

259240

问题描述

你得到一个长度为 $N$ 的字符串 $S$，由字符 'A'，'B' 和 '?' 组成。

同时，你得到一个正整数 $K$。 一个由 'A' 和 'B' 组成的字符串 $T$ 被认为是 好字符串，如果满足以下条件：

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

字符串 $S$ 中有 $q$ 个 '?' 字符。通过将 $S$ 中的每个 '?' 替换为 'A' 或 'B'，可以得到 $2^q$ 个字符串。找出这些字符串中有多少个是好字符串。

由于计数可能非常大，所以需要对 $998244353$ 取模。

约束

• $2 \leq K \leq N \leq 1000$
• $K \leq 10$
• $S$ 是由 'A'，'B' 和 '?' 组成的字符串。
• $S$ 的长度为 $N$。
• $N$ 和 $K$ 是整数。

输入

输入从标准输入中给出，格式如下：

$N$ $K$
$S$

输出

输出答案。

样例输入 1

7 4
AB?A?BA

样例输出 1

1

给定的字符串有两个 '?'。通过将每个 '?' 替换为 'A' 或 'B'，可以得到四个字符串：

• ABAAABA
• ABAABBA
• ABBAABA
• ABBABBA

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

因此，你应该输出 1。

样例输入 2

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

样例输出 2

116295436

确保计算出的好字符串数量对 $998244353$ 取模。

样例输入 3

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

样例输出 3

0

可能存在无法通过替换 '?' 获得好字符串的情况。

样例输入 4

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

样例输出 4

259240