AT_arc119_f [ARC119F] AtCoder Express 3

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$ 取模的结果。

### 限制条件 - $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 翻译