Routing Schemes

A network has $N$ nodes ($2\le N\le 100$) labeled $1$ through $N$. Each node is a sender, a receiver, or neither. The number of senders $S$ equals the number of receivers, and $S \ge 1$.

The connections are a list of directed edges $i \to j$, meaning node $i$ may route to node $j$. Every edge satisfies $i<j$, except exactly $K$ edges that satisfy $i>j$ ($0 \le K \le 2$). There are no self-loops ($i \to i$).

A routing scheme is a set of $S$ directed paths, each going from a sender to a receiver. No two paths share an endpoint, so the paths connect distinct senders to distinct receivers. A path $s=v_0 \to v_1 \to v_2 \to \cdots \to v_e=r$ is valid when the edge $v_i \to v_{i+1}$ exists for every $0 \le i < e$. A node may appear more than once in the same path.

Count the routing schemes in which every directed edge is traversed exactly once. The answer may be very large, so print it modulo $10^9+7$. Each test case has at least one valid routing scheme.

The first line contains $T$, the number of test cases ($1 \le T \le 20$). Solve each test case independently. The sum of $N^2$ over all test cases does not exceed $2 \cdot 10^4$.

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

The second line is a string of length $N$. The $i$-th character is S if node $i$ is a sender, R if node $i$ is a receiver, and . if it is neither. The number of Rs equals the number of Ss, and there is at least one S.

The next $N$ lines each contain a bit string of length $N$. The $j$-th bit of the $i$-th line is 1 if there is a directed edge from node $i$ to node $j$, and 0 otherwise. The main diagonal is all zeros. Exactly $K$ ones lie below the main diagonal.

For each test case, print the number of routing schemes in which every edge is traversed exactly once, modulo $10^9+7$, on its own line.