[ABC359] D - Avoid K Palindrome

D - Avoid K Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 450 分

题面

给定一个长度为 的字符串 ，由字符 A、B 和 ? 组成。

还给定一个正整数 。如果一个只包含 A 和 B 的字符串 满足以下条件，则称其为好字符串:

• 中长度为 的任意连续子串不是回文串。

设 为 中包含的 ? 字符的数量。将 中的每个 ? 替换为 A 或 B，共有 个字符串。求出其中有多少个字符串是好字符串。

计数可能非常大，所以要对 取模。

限制条件

• 是一个由 A、B 和 ? 组成的字符串。
• 的长度为 。
• 和 是整数。

---

输入

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

输出

输出答案。

---

输入样例 1

7 4
AB?A?BA

输出样例 1

1

给定的字符串中有两个 ?。将每个 ? 替换为 A 或 B 可得到四个字符串:

• ABAAABA
• ABAABBA
• ABBAABA
• ABBABBA

在这四个字符串中，最后三个包含长度为 4 的回文子串 ABBA，因此它们不是好字符串。

因此，答案为 1。

---

输入样例 2

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

输出样例 2

116295436

记得要对 取模后输出好字符串的数量。

---

输入样例 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