Score : $450$ points

问题陈述

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

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

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

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

计数可能会非常大，因此需要找到它对 $998244353$ 取模的结果。

以上为大语言模型 kimi 翻译，仅供参考。

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