Problem Description

Consider a network consisting of $N$ nodes numbered $1 \dots N$. Each node is designated as a sender, a receiver, or neither. The number of senders $S$ is equal to the number of receivers ($S \geq 1$).

The connections between nodes in this network can be represented by a series of directed edges in the form $i \rightarrow j$, indicating that node $i$ can route to node $j$. Interestingly, all edges satisfy the property $i < j$, except for $K$ edges that satisfy $i > j$ ($0 \leq K \leq 2$). There are no self-loops (edges of the form $i \rightarrow i$).

A "routing scheme" consists of $S$ directed paths from senders to receivers, where no two paths have the same start and end points. These paths connect different senders to different receivers. A path from sender $s$ to receiver $r$ can be represented by a sequence of nodes $s = v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_e = r$, where for all $0 \leq i < e$, the directed edge $v_i \rightarrow v_{i+1}$ exists. A node may appear multiple times within the same path.

Calculate the number of routing schemes such that each directed edge is used exactly once. Since the answer may be very large, output the answer modulo $10^9 + 7$. The input guarantees that there is at least one valid routing scheme.

The input contains $T$ test cases that need to be solved independently.

Input Format

The first line of the input contains $T$, the number of test cases.

Each test case begins with a line containing the integers $N$ and $K$. Note that $S$ is not explicitly given in the input.

The second line of each test case contains a string of length $N$. If the $i$-th node is a sender, the $i$-th character of the string is $\texttt{S}$; if it is a receiver, it is $\texttt{R}$; if it is neither, it is $\texttt{.}$. The number of $\texttt{R}$'s in the string equals the number of $\texttt{S}$'s, and there is at least one $\texttt{S}$.

The next $N$ lines of each test case each contain a string of length $N$ consisting of 0s and 1s. If there is a directed edge from node $i$ to node $j$, the $j$-th character of the $i$-th line is $1$; otherwise, it is $0$. Due to the absence of self-loops, the main diagonal of the matrix contains only $0$s. Additionally, there are exactly $K$ $1$s below the main diagonal.

For readability, a blank line separates adjacent test cases.

Output Format

For each test case, output the number of routing schemes where each edge is used exactly once, modulo $10^9 + 7$. The input guarantees that there is at least one valid routing scheme for each test case.

Sample Input and Output

Input Sample #1

2

8 0
SS....RR
00100000
00100000
00011000
00000100
00000100
00000011
00000000
00000000

13 0
SSS.RRRSS.RR.
0001000000000
0001000000000
0001000000000
0000111000000
0000000000000
0000000000000
0000000000000
0000000001000
0000000001000
0000000000110
0000000000000
0000000000000
0000000000000

Output Sample #1

4
12

Input Sample #2

2

5 1
SS.RR
00101
00100
10010
00000
00000

6 2
S....R
001000
000100
010001
000010
001000
000000

Output Sample #2

3
1

Input Sample #3

5

3 2
RS.
010
101
100

4 2
.R.S
0100
0010
1000
0100

4 2
.SR.
0000
0011
0100
0010

5 2
.SSRR
01000
10101
01010
00000
00000

6 2
SS..RR
001010
000010
000010
000010
100101
000000

Output Sample #3

2
1
2
6
24

Notes/Hints

Sample 1 Explanation

For the first test case, the edges in the network are $1 \rightarrow 3, 2 \rightarrow 3, 3 \rightarrow 4, 3 \rightarrow 5, 4 \rightarrow 6, 5 \rightarrow 6, 6 \rightarrow 7, 6 \rightarrow 8$.

There are four possible routing schemes:

• $1 \rightarrow 3 \rightarrow 4 \rightarrow 6 \rightarrow 7, 2 \rightarrow 3 \rightarrow 5 \rightarrow 6 \rightarrow 8$
• $1 \rightarrow 3 \rightarrow 5 \rightarrow 6 \rightarrow 7, 2 \rightarrow 3 \rightarrow 4 \rightarrow 6 \rightarrow 8$
• $1 \rightarrow 3 \rightarrow 4 \rightarrow 6 \rightarrow 8, 2 \rightarrow 3 \rightarrow 5 \rightarrow 6 \rightarrow 7$
• $1 \rightarrow 3 \rightarrow 5 \rightarrow 6 \rightarrow 8, 2 \rightarrow 3 \rightarrow 4 \rightarrow 6 \rightarrow 7$

For the second test case, the edges in the network are $1 \rightarrow 4, 2 \rightarrow 4, 3 \rightarrow 4, 4 \rightarrow 5, 4 \rightarrow 6, 4 \rightarrow 7, 8 \rightarrow 10, 9 \rightarrow 10, 10 \rightarrow 11, 11 \rightarrow 12$.

One possible routing scheme consists of the following paths:

• $1 \rightarrow 4 \rightarrow 5$
• $2 \rightarrow 4 \rightarrow 7$
• $3 \rightarrow 4 \rightarrow 6$
• $8 \rightarrow 10 \rightarrow 12$
• $9 \rightarrow 10 \rightarrow 11$

Overall, senders ${1, 2, 3}$ can route to receivers ${5, 6, 7}$ in some permutation, and senders ${8, 9}$ can route to receivers ${11, 12}$ in some permutation, yielding an answer of $6 \times 2 = 12$.

Sample 2 Explanation

For the first test case, the edges in the network are $1 \rightarrow 3, 1 \rightarrow 5, 2 \rightarrow 3, 3 \rightarrow 1, 3 \rightarrow 4$.

There are three possible routing schemes:

• $1 \rightarrow 3 \rightarrow 1 \rightarrow 5, 2 \rightarrow 3 \rightarrow 4$
• $1 \rightarrow 3 \rightarrow 4, 2 \rightarrow 3 \rightarrow 1 \rightarrow 5$
• $1 \rightarrow 5, 2 \rightarrow 3 \rightarrow 1 \rightarrow 3 \rightarrow 4$

For the second test case, the edges in the network are $1 \rightarrow 3, 2 \rightarrow 4, 3 \rightarrow 2, 3 \rightarrow 6, 4 \rightarrow 5, 5 \rightarrow 3$.

There is only one possible routing scheme: $1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 6$.

Data Range and Constraints

$2 \leq N \leq 100$, $1 \leq T \leq 20$, $\sum N^2 \leq 2 \times 10^4$.

见题面 Input 部分

见题面 Output 部分