分数: 800 点
问题陈述
有 N+1 车站,编号 0 通过 N。以前,它只有 普通列车,在车站之间运行 i 和 i + 1 在任一方向上各一分钟 i (0 \leq i \leq N-1).
然而有一天,铁路公司分成了两组,称为 高速 (光速)和 俊奎 (半快递)。他们决定除车站外的每个车站 0 和 N 应由其中一组进行管理。管理站的组 j (1 \leq j \leq N-1) 用一个字符表示 c_j: A 表示 Ko-soku 管理该站, B 指 Jun-kyu 管理该站,并且 ? 表示尚未决定。自站 0 和 N 非常重要,两个小组都会管理它们。
现在,除了普通列车外,Ko-soku 和 Jun-kyu 决定运营两种新型列车。
高速列车: 让站 a_0, a_1, \dots, a_s 是 Ko-soku 按升序排列的管理站。这些火车在车站之间运行 a_k 和 a_{k+1} 在任一方向上各一分钟 k.
俊奎列车: 让站 b_0, b_1, \dots, b_t 是 Jun-kyu 按升序排列的管理站。这些火车在车站之间运行 b_k 和 b_{k+1} 在任一方向上各一分钟 k.
有 2^q 这些火车的运行方式、地点 q 是数量 ?s。其中,有多少使我们能够从车站出发 0 到 车站 N 不超过 K 车程几分钟?求这个计数的模数 (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} is
A,B,或?.
输入
输入由标准输入按以下格式给出:
N K
c_1c_2\cdotsc_{N-1}
输出
打印计数模数 (10^9+7).
样本输入 1
8 3 A??AB?B
示例输出 1
4
这里有 2^3 = 8 火车运行的可能方式。其中,以下四种使我们能够从车站前往 0 到 车站 8 不超过 3 分钟车程。
- 如果 Ko-soku 管理车站 2, 3, 6,我们可以去车站 0 \rightarrow 5 \rightarrow 7 \rightarrow 8,如下图#1所示。
- 如果 Ko-soku 管理车站 2, 3 和 Jun-kyu 管理车站 6,我们可以去车站 0 \rightarrow 5 \rightarrow 4 \rightarrow 8,如下图#2所示。
- 如果高速管理站 2 和 Jun-kyu 管理车站 3, 6,我们可以去车站 0 \rightarrow 3 \rightarrow 4 \rightarrow 8,如下图#4所示。
- 如果俊奎管理车站 2, 3, 6,我们可以去车站 0 \rightarrow 1 \rightarrow 4 \rightarrow 8,如下图#8所示。
因此,答案是 4。下图显示了所有可能的方式,其中红色车站和铁路仅由 Ko-soku 管理,蓝色车站和铁路仅由 Jun-kyu 管理。

示例输入 2
11 6 ???B??A???
示例输出 2
256
在这里,所有的 2^8 = 256 我们从车站出发的方式 0 到 车站 11 不超过 6 分钟车程。
示例输入 3
16 5 ?A?B?A?B?A?B?A?
示例输出 3
10
10 下图所示的路线可以让我们从车站前往 0 到 车站 16 不超过 5 分钟车程。

示例输入 4
119 15 ????????A?????????????????????????BA????????????????????????AB???????A???????????B?????????????????????????????A??????
示例输出 4
313346281
有 1623310324709451 理想的方法。打印此计数的模数 (10^9 + 7),即 313346281.