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).

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).

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 ?.

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.

见题面 Input 部分

见题面 Output 部分