← 返回题目列表

AtCoder · arc119_f

F. AtCoder特快3

中文机器翻译题面 查看原题

分数: 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.