考虑一个包含 $N$ ($2\le N\le 100$) 个节点的网络，节点编号为 $1\ldots N$。每个节点被指定为发送方、接收方或两者皆非。发送方的数量 $S$ 等于接收方的数量 ($S\ge 1$)。
网络中节点之间的连接由一系列有向边描述，每条边形式为 $i\to j$，表示节点 $i$ 可以路由到节点 $j$。有趣的是，除了 $K$ 条满足 $i>j$ 的边之外，所有边都满足 $i “路由方案”的描述由一组从发送方到接收方的 $S$ 条有向路径组成，使得这 $S$ 条路径中没有两条路径共享一个端点。也就是说，这些路径连接了不同的发送方到不同的接收方。从发送方 $s$ 到接收方 $r$ 的路径可以描述为节点序列 $$s=v_0\to v_1 \to v_2\to \cdots \to v_e=r$$ 使得对于所有 $0\le i 计算满足每条有向边恰好被遍历一次的路由方案总数。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。题目保证至少存在一种满足这些约束的路由方案。 每个输入包含 $T$ ($1\le T\le 20$) 个测试用例，应独立求解。保证所有测试用例的 $N^2$ 之和不超过 $2\cdot 10^4$。 第一行包含 $T$，即测试用例的数量。 每个测试用例的第一行包含整数 $N$ 和 $K$。注意 $S$ 不会在输入中显式给出。 每个测试用例的第二行包含一个长度为 $N$ 的字符串。如果第 $i$ 个节点是发送方，则字符串的第 $i$ 个字符为 S；如果是接收方，则为 R；如果两者皆非，则为 .。字符串中 R 的数量等于 S 的数量，且至少存在一个 S。 接下来的 $N$ 行，每行包含一个长度为 $N$ 的由 0 和 1 组成的位串。如果存在从节点 $i$ 到节点 $j$ 的有向边，则第 $i$ 行的第 $j$ 位为 1，否则为 0。由于不存在自环，矩阵的主对角线全为 0。此外，主对角线下方恰好有 $K$ 个 1。 连续的测试用例之间用换行符分隔，以提高可读性。 对于每个测试用例，输出满足每条边恰好被遍历一次的路由方案数量，对 $10^9+7$ 取模。保证每个测试用例至少存在一种有效的路由方案。输入格式
输出格式
样例
样例输入 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
样例输出 1
4
12
样例输入 2
2
5 1
SS.RR
00101
00100
10010
00000
00000
6 2
S....R
001000
000100
010001
000010
001000
000000
样例输出 2
3
1
样例输入 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
样例输出 3
2
1
2
6
24
子任务