配点: $800$ 点

問題文

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$ で割った余りを求めてください。

制約

• $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、? のいずれか

入力

入力は以下の形式で標準入力から与えられます。

$N$ $K$

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

出力

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

8 3
A??AB?B

4

ここでは $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$ 通りとなります。これを図で表すと、以下のようになります。下図においては、赤色が光速派のみが管理する駅や光速列車の路線、青色が準急派のみが管理する駅や準急列車の路線を表すものとします。

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

256

ここでは、$2^8 = 256$ 通りの組み合わせすべてについて、駅 $0$ から駅 $11$ まで $6$ 分以内の乗車で行くことが可能です。

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

10

以下の図に示される $10$ 通りの組み合わせについて、駅 $0$ から駅 $16$ まで $5$ 分以内の乗車で行くことが可能です。

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

313346281

条件を満たすものは $1623310324709451$ 通りありますが、これを $10^9 + 7$ で割った余りである $313346281$ を出力してください。