/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点: 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_1c_2\cdotsc_{N-1}
出力
答えを 10^9+7 で割った余りを出力してください。
入力例 1
8 3 A??AB?B
出力例 1
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 通りとなります。これを図で表すと、以下のようになります。下図においては、赤色が光速派のみが管理する駅や光速列車の路線、青色が準急派のみが管理する駅や準急列車の路線を表すものとします。
入力例 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 を出力してください。
Score: 800 points
Problem Statement
There are N+1 stations along the AtCoder Line, numbered 0 through N. Formerly, it only had Local Trains, which run between Stations i and i + 1 in one minute in either direction for each i (0 \leq i \leq N-1).
One day, however, the railway company broke into two groups, called Ko-soku (light speed) and Jun-kyu (semi express). They decided that each station other than Stations 0 and N should be administered by one of the groups. The group that administers Station j (1 \leq j \leq N-1) is represented by a character c_j: A means that Ko-soku administers the station, B means Jun-kyu administers the station, and ? means it is undecided. Since Stations 0 and N are so important, both groups will administer them.
Now, Ko-soku and Jun-kyu have decided to run two new types of trains, in addition to the local trains.
Ko-soku Trains: Let Stations a_0, a_1, \dots, a_s be the stations administered by Ko-soku in ascending order. These trains run between Stations a_k and a_{k+1} in one minute in either direction for each k.
Jun-kyu Trains: Let Stations b_0, b_1, \dots, b_t be the stations administered by Jun-kyu in ascending order. These trains run between Stations b_k and b_{k+1} in one minute in either direction for each k.
There are 2^q ways in which these trains run, where q is the number of ?s. Among them, how many enables us to go from Station 0 to Station N in no more than K minutes' ride? Find this count modulo (10^9+7).
Constraints
- 2 \leq N \leq 4000
- 1 \leq K \leq \frac{N+1}{2}
- N and K are integers.
- Each of c_1, c_2, \dots, c_{N-1} is
A,B, or?.
Input
Input is given from Standard Input in the following format:
N K
c_1c_2\cdotsc_{N-1}
Output
Print the count modulo (10^9+7).
Sample Input 1
8 3 A??AB?B
Sample Output 1
4
Here, there are 2^3 = 8 possible ways in which the trains run. Among them, the following four enable us to go from Station 0 to Station 8 in no more than 3 minutes' ride.
- If Ko-soku administers Stations 2, 3, 6, we can go Station 0 \rightarrow 5 \rightarrow 7 \rightarrow 8, as shown at #1 in the figure below.
- If Ko-soku administers Stations 2, 3 and Jun-kyu administers Station 6, we can go Station 0 \rightarrow 5 \rightarrow 4 \rightarrow 8, as shown at #2 in the figure below.
- If Ko-soku administers Station 2 and Jun-kyu administers Stations 3, 6, we can go Station 0 \rightarrow 3 \rightarrow 4 \rightarrow 8, as shown at #4 in the figure below.
- If Jun-kyu administers Stations 2, 3, 6, we can go Station 0 \rightarrow 1 \rightarrow 4 \rightarrow 8, as shown at #8 in the figure below.
Therefore, the answer is 4. The figure below shows all the possible ways, where red stations and railways are administered only by Ko-soku, and blue stations and railways are administered only by Jun-kyu.
Sample Input 2
11 6 ???B??A???
Sample Output 2
256
Here, all of the 2^8 = 256 ways enable us to go from Station 0 to Station 11 in no more than 6 minutes' ride.
Sample Input 3
16 5 ?A?B?A?B?A?B?A?
Sample Output 3
10
10 ways shown in the figure below enable us to go from Station 0 to Station 16 in no more than 5 minutes' ride.
Sample Input 4
119 15 ????????A?????????????????????????BA????????????????????????AB???????A???????????B?????????????????????????????A??????
Sample Output 4
313346281
There are 1623310324709451 desirable ways. Print this count modulo (10^9 + 7), that is, 313346281.