[ARC119F] AtCoder Express 3

有 $N+1$ 个点 ，标号为 $0$ 到 $N$ 。对于 $i \ (0\leq i \leq N-1)$ ，存在一条无向边连接 点 $i$ 和点 $i+1$ 。 有 $A$ 和 $B$ 两种类型的点，每个点与其最近的同类型点有一条无向边相连。特别的，点 $0$ 和点 $N$ 既属于 $A$ 类型点也属于 $B$ 类型点。 部分点已确认类型，对剩下点分类，求有多少种分类方式使得 $0$ 到 $N$ 存在一条长度小于等于 $K$ 的路径 $(\rm mod \ 10^{9}+7)$ 。 - $ 2\ \leq\ N\ \leq\ 4000 $ - $ 1\ \leq\ K\ \leq\ \frac{N+1}{2} $

[problemUrl]: https://atcoder.jp/contests/arc119/tasks/arc119_f AtCoder 鉄道には $ N+1 $ 個の駅があり、駅には $ 0 $ から $ N $ までの番号が付けられています。ここではかつて、各 $ i $ $ (0\ \leq\ i\ \leq\ N-1) $ に対して駅 $ i $ と駅 $ i+1 $ の間を双方向に $ 1 $ 分で走行する **普通列車** のみが運行されていました。 しかし、ある日鉄道会社は「光速派」と「準急派」の $ 2 $ つのグループに分裂し、駅 $ 0 $ と駅 $ N $ を除く各駅は光速派と準急派のうち片方が管理することになりました。駅 $ j $ $ (1\ \leq\ j\ \leq\ N-1) $ を管理するグループは文字 $ c_j $ で表され、`A` は光速派が、`B` は準急派が管理すること、`?` はまだ決まっていないことを表します。駅 $ 0 $ と駅 $ N $ は重要な駅なので、両方が管理します。 ここで、光速派と準急派は、普通列車に加えて新たに $ 2 $ 種類の鉄道路線を作ることにしました。 > **光速列車**：光速派が管理する駅の番号を昇順に $ 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 $ 通り考えられます。その中で、$ K $ 分以内の乗車で駅 $ 0 $ から駅 $ N $ に行けるようになるものは何通りあるでしょうか？これを $ 10^9+7 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ c_1 $$ c_2 $$ \cdots $$ c_{N-1} $

答えを $ 10^9+7 $ で割った余りを出力してください。

8 3
A??AB?B

4

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

256

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

10

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`、`?` のいずれか ### Sample Explanation 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 $ 通りとなります。これを図で表すと、以下のようになります。下図においては、赤色が光速派のみが管理する駅や光速列車の路線、青色が準急派のみが管理する駅や準急列車の路線を表すものとします。 !\[ \](https://img.atcoder.jp/arc119/db3f88315c456535f7ce57116009c126.png) ### Sample Explanation 2 ここでは、$ 2^8\ =\ 256 $ 通りの組み合わせすべてについて、駅 $ 0 $ から駅 $ 11 $ まで $ 6 $ 分以内の乗車で行くことが可能です。 ### Sample Explanation 3 以下の図に示される $ 10 $ 通りの組み合わせについて、駅 $ 0 $ から駅 $ 16 $ まで $ 5 $ 分以内の乗車で行くことが可能です。 !\[ \](https://img.atcoder.jp/arc119/4b879e19b8c1cd7eac9d52eb0ea58e5c.png) ### Sample Explanation 4 条件を満たすものは $ 1623310324709451 $ 通りありますが、これを $ 10^9\ +\ 7 $ で割った余りである $ 313346281 $ を出力してください。