P7531 [USACO21OPEN] Routing Schemes P

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 $ij$ ($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.

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.

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.

#### 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