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 \ge 1$).

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

A routing scheme is described by $S$ directed paths from senders to receivers, where no two paths share the same start or end node. In other words, these paths connect distinct senders to distinct receivers. A path from sender $s$ to receiver $r$ can be written as a sequence of nodes $s=v_0 \to v_1 \to v_2 \to \cdots \to v_e=r$, where for all $0 \le i < e$, the directed edge $v_i \to v_{i+1}$ exists. A node may appear more than once in the same path.

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

Each input contains $T$ test cases that should be solved independently.

Input Format

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

The first line of each test case contains integers $N$ and $K$. Note that $S$ is not given explicitly in the input.

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

Each of the next $N$ lines of a test case contains a 01 string of length $N$. If there is a directed edge from node $i$ to node $j$, then the $j$-th character of the $i$-th line is $1$, otherwise it is $0$. Since there are no self-loops, the main diagonal of the matrix contains only $0$. Besides this, there are exactly $K$ $1$'s below the main diagonal.

For readability, adjacent test cases are separated by a blank line.

Output Format

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

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

4
12

2

5 1
SS.RR
00101
00100
10010
00000
00000

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

3
1

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

2
1
2
6
24

Hint

Explanation of Sample 1

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

There are four possible routing schemes:

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

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

One possible routing scheme consists of the following paths:

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

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

Explanation of Sample 2

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

There are three possible routing schemes:

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

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

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

Constraints

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

Translated by ChatGPT 5