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