Problem10891--ABC359 - D - Avoid K Palindrome

10891: ABC359 - D - Avoid K Palindrome

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

SubmitSolved: 2Submit Num: 2StatisticsShowOff!

Description

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$.

Input

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

```
$N$ $K$
$S$
```

Output

Print the answer.

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.

Sample 1 Input 

7 4
AB?A?BA

Sample 1 Output 

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 2 Input 

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

Sample 2 Output 

116295436

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

Sample 3 Input 

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

Sample 3 Output 

0

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

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


259240

Source/Category

 
Submit