Erase the Unwanted Patterns

DreamGrid has a paper strip with \(n\) grids in a line. Each grid either contains DreamGrid's pattern, BaoBao's pattern or is empty. The grids are numbered from 1 to \(n\) from left to right. Unfortunately, when DreamGrid was away, his roommate BaoBao drew some patterns in some grids. Now DreamGrid must remove all of BaoBao's patterns without erasing his own.

In each operation, DreamGrid may choose two integers \(l\) and \(r\) satisfying \(1 \le l \le r \le n\) such that every grid \(i\) with \(l \le i \le r\) is either empty or contains BaoBao's pattern. He then erases the patterns in all these grids (i.e. sets them to empty).

DreamGrid performs exactly \(m\) operations. Two operation sequences \(\{(a_1,b_1), (a_2,b_2), \dots, (a_m,b_m)\}\) and \(\{(c_1,d_1), (c_2,d_2), \dots, (c_m,d_m)\}\) are considered different if there exists an index \(k\) (\(1 \le k \le m\)) such that \(a_k \ne c_k\) or \(b_k \ne d_k\).

Originally, the state of the strip is given by a string of length \(n\) consisting of characters:

• D indicating a grid with DreamGrid's pattern,
• B indicating a grid with BaoBao's pattern,
• . indicating an empty grid.

Your task is to compute the number of valid erasing sequences that will remove all grids originally containing BaoBao's pattern, using exactly \(m\) operations. Since the answer may be large, output it modulo \(10^9+7\).

Note: An operation can only be applied to a contiguous segment of grids that does not include any grid with DreamGrid's pattern. The operations in different segments (separated by a grid with DreamGrid's pattern) are independent; however, the interleaving order of the operations also counts toward different sequences.

The problem can be approached by splitting the strip into segments separated by grids with DreamGrid's pattern. In each segment (which contains no D), if there are grids with BaoBao's pattern then the operations performed on that segment must cover all such positions. Let the total number of intervals in a segment of length \(L\) be \(T = \frac{L(L+1)}{2}\). For a set \(X\) of BaoBao positions in the segment, define \(f(X)\) as the sum of the numbers of intervals available in the gaps (maximal continuous empty portions) when the positions in \(X\) are removed. Using inclusion–exclusion, the number of ways to choose \(r\) operations on that segment that cover all BaoBao's patterns is given by \[ g(r)=\sum_{X\subseteq S}(-1)^{|X|}\,(f(X))^r, \] where \(S\) is the set of indices with BaoBao's pattern in that segment (with 1-indexing within the segment) and by convention \(f(\emptyset)=T\). Then using generating functions and accounting for the interleaving among segments, the final answer is computed.

It is guaranteed that the input sizes are small so that a solution using subset enumeration over BaoBao's pattern positions in each segment will run in time.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of grids and the number of operations, respectively).

The second line contains a string of length \(n\) consisting only of characters D, B and ., representing the initial state of each grid.

outputFormat

Output a single integer: the number of valid erasing sequences modulo \(10^9+7\).

sample

5 1
B...B

1