问题描述

在 AtCoder Line 上有 $N+1$ 个车站，编号从 $0$ 到 $N$。以前，它只有Local Trains，在每个 $i$ $(0 \leq i \leq N-1)$ 的两个方向上，在车站 $i$ 和车站 $i + 1$ 之间的行驶时间为一分钟。

然而，有一天，铁路公司分为两个组，称为 Ko-soku（光速）和 Jun-kyu（半快车）。他们决定除了车站 $0$ 和 $N$ 之外的每个站点都应该由其中一个组管理。管理车站 $j$ $(1 \leq j \leq N-1)$ 的组别用字符 $c_j$ 表示：A 表示 Ko-soku 管理该站点，B 表示 Jun-kyu 管理该站点，? 表示尚未确定。由于车站 $0$ 和 $N$ 非常重要，两个组都会管理这两个车站。

现在，Ko-soku 和 Jun-kyu 决定除了 Local Trains 之外，还将运行两种新型的列车。

**Ko-soku Trains：**假设 Stations $a_0, a_1, \dots, a_s$ 按升序是由 Ko-soku 管理的车站。这些列车在每个 $k$ 的两个方向上，在车站 $a_k$ 和车站 $a_{k+1}$ 之间的行驶时间为一分钟。

**Jun-kyu Trains：**假设 Stations $b_0, b_1, \dots, b_t$ 按升序是由 Jun-kyu 管理的车站。这些列车在每个 $k$ 的两个方向上，在车站 $b_k$ 和车站 $b_{k+1}$ 之间的行驶时间为一分钟。

这些列车的运行方式有 $2^q$ 种，其中 $q$ 是 ? 的数量。其中有多少种方式可以在不超过 $K$ 分钟的时间内从 Station $0$ 到达 Station $N$？请找出这个计数结果对 $(10^9+7)$ 取模的结果。

约束条件

• $2 \leq N \leq 4000$
• $1 \leq K \leq \frac{N+1}{2}$
• $N$ 和 $K$ 是整数。
• $c_1, c_2, \dots, c_{N-1}$ 中的每个字符都是 A、B 或 ?。

---

输入

输入以以下格式从标准输入给出：

$N$ $K$ $c_1$$c_2$$\cdots$$c_{N-1}$

输出

输出结果对 $(10^9+7)$ 取模后的计数结果。

---

示例输入 1

8 3
A??AB?B

示例输出 1

4

这里，有 $2^3 = 8$ 种列车运行的可能方式。其中，以下四种方式使我们可以在不超过 $3$ 分钟的时间内从 Station $0$ 到达 Station $8$。

• 如果 Ko-soku 管理 Stations $2, 3, 6$，我们可以按照图中 #1 所示的路径行驶：Station $0 \rightarrow 5 \rightarrow 7 \rightarrow 8$。
• 如果 Ko-soku 管理 Stations $2, 3$，Jun-kyu 管理 Station $6$，我们可以按照图中 #2 所示的路径行驶：Station $0 \rightarrow 5 \rightarrow 4 \rightarrow 8$。
• 如果 Ko-soku 管理 Station $2$，Jun-kyu 管理 Stations $3, 6$，我们可以按照图中 #4 所示的路径行驶：Station $0 \rightarrow 3 \rightarrow 4 \rightarrow 8$。
• 如果 Jun-kyu 管理 Stations $2, 3, 6$，我们可以按照图中 #8 所示的路径行驶：Station $0 \rightarrow 1 \rightarrow 4 \rightarrow 8$。

因此，答案是 $4$。下图显示了所有可能的路径，其中红色的车站和铁路只由 Ko-soku 管理，蓝色的车站和铁路只由 Jun-kyu 管理。

---

示例输入 2

11 6
???B??A???

示例输出 2

256

这里，所有 $2^8 = 256$ 种方式都使我们可以在不超过 $6$ 分钟的时间内从 Station $0$ 到达 Station $11$。

---

示例输入 3

16 5
?A?B?A?B?A?B?A?

示例输出 3

10

下图中的 $10$ 种方式使我们可以在不超过 $5$ 分钟的时间内从 Station $0$ 到达 Station $16$。

---

示例输入 4

119 15
????????A?????????????????????????BA????????????????????????AB???????A???????????B?????????????????????????????A??????

示例输出 4

313346281

有 $1623310324709451$ 种合适的方式。请对该计数结果取模 $(10^9 + 7)$，即 $313346281$。