题目描述

AtCoder 铁道有 $N+1$ 个车站，车站编号从 $0$ 到 $N$。过去，每个 $i$（$0 \leq i \leq N-1$）之间仅有普通列车运行，普通列车可以在车站 $i$ 和车站 $i+1$ 之间双向行驶，每次耗时 $1$ 分钟。

然而，某一天，铁道公司分裂为“光速派”和“准急派”两个集团，除了车站 $0$ 和车站 $N$ 以外，其余每个车站都由这两派中的一方管理。对于车站 $j$（$1 \leq j \leq N-1$），其管理方用字符 $c_j$ 表示，A 表示由光速派管理，B 表示由准急派管理，? 表示尚未决定。车站 $0$ 和车站 $N$ 是重要车站，由双方共同管理。

在此基础上，光速派和准急派决定，除了普通列车外，各自再新建一种铁道路线：

光速列车：将光速派管理的车站编号按升序记为 $a_0, a_1, \dots, a_s$，对于每个 $k$，在车站 $a_k$ 和 $a_{k+1}$ 之间新建一条双向线路，每次耗时 $1$ 分钟。

准急列车：将准急派管理的车站编号按升序记为 $b_0, b_1, \dots, b_t$，对于每个 $k$，在车站 $b_k$ 和 $b_{k+1}$ 之间新建一条双向线路，每次耗时 $1$ 分钟。

记 ? 的个数为 $q$，则所有可能的铁道路线共有 $2^q$ 种。在这些方案中，有多少种可以使得从车站 $0$ 出发，在 $K$ 分钟以内到达车站 $N$？请输出方案数对 $10^9+7$ 取模的结果。

输入格式

输入按以下格式从标准输入读入：

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

输出格式

输出方案数对 $10^9+7$ 取模的结果。

样例 1

输入

8 3
A??AB?B

输出

4

样例 2

输入

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

输出

256

样例 3

输入

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

输出

10

样例 4

输入

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

输出

313346281

说明/提示

限制条件

• $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 或 ?

样例解释 1

此时共有 $2^3 = 8$ 种铁道路线，其中有以下 $4$ 种可以在 $3$ 分钟以内从车站 $0$ 到达车站 $8$：

• 车站 $2, 3, 6$ 均由光速派管理：可按 $0 \rightarrow 5 \rightarrow 7 \rightarrow 8$ 行驶（对应下图 #1）
• 车站 $2, 3$ 由光速派管理，车站 $6$ 由准急派管理：可按 $0 \rightarrow 5 \rightarrow 4 \rightarrow 8$ 行驶（对应下图 #2）
• 车站 $2$ 由光速派管理，车站 $3, 6$ 由准急派管理：可按 $0 \rightarrow 3 \rightarrow 4 \rightarrow 8$ 行驶（对应下图 #4）
• 车站 $2, 3, 6$ 均由准急派管理：可按 $0 \rightarrow 1 \rightarrow 4 \rightarrow 8$ 行驶（对应下图 #8）

因此答案为 $4$。下图中，红色表示仅由光速派管理的车站及其光速列车线路，蓝色表示仅由准急派管理的车站及其准急列车线路。

样例解释 2

此时 $2^8 = 256$ 种组合下，所有方案都可以在 $6$ 分钟以内从车站 $0$ 到达车站 $11$。

样例解释 3

下图所示的 $10$ 种组合可以在 $5$ 分钟以内从车站 $0$ 到达车站 $16$。

样例解释 4

满足条件的方案有 $1623310324709451$ 种，对 $10^9+7$ 取模后输出 $313346281$。

由 ChatGPT 4.1 翻译