#USACOC2111B. Routing Schemes

Routing Schemes

Consider a network of NN nodes labeled 1N1 \ldots N. Each node is designated as a sender, a receiver, or neither. The number of senders, S, is equal to the number of receivers.

The connections between the nodes in this network can be described by a list of directed edges each of the form iji \to j, meaning that node i may route to node j. Interestingly, all of these edges satisfy the property that i<ji \lt j, aside from KK that satisfy i>ji \gt j. There are no self-loops (edges of the form iii \to i).

The description of a "routing scheme" consists of a set of SS directed paths from senders to receivers such that no two of these paths share an endpoint. That is, the paths connect distinct senders to distinct receivers. A path from a sender ss to a receiver rr can be described as a sequence of nodes

s=v0v1v2ve=rs=v_0 \to v_1 \to v_2 \to \cdots \to v_e=r

such that the directed edges vivi+1v_i \to v_i+1 exist for all 0i<e0 \leqslant i \lt e. A node may appear more than once within the same path.

Count the number of distinct routing schemes such that every directed edge is traversed exactly once. Since the answer may be very large, report it modulo 109+710^9+7. It is guaranteed that there is at least one routing scheme satisfying these constraints.

Each input contains TT test cases that should be solved independently. It is guaranteed that the sum of N2N^2 over all test cases does not exceed 21042 \cdot 10^4.

  • 2N1002 \leqslant N \leqslant 100
  • S1S \geqslant 1
  • 0K20 \leqslant K \leqslant 2
  • 1T201 \leqslant T \leqslant 20

Input Format

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

The first line of each test case contains the integers NN and KK. Note that SS is not explicitly given within the input.

The second line of each test case contains a string of length NN. The ii-th character of the string is equal to S if the ii-th node is a sender, R if the ii-th node is a receiver, or . if the ii-th node is neither. The number of Rs in this string is equal to the number of Ss, and there is at least one S.

The next NN lines of each test case each contain a bit string of NN zeros and ones. The jj-th bit of the ii-th line is equal to 11 if there exists a directed edge from node ii to node jj, and 00 otherwise. As there are no self-loops, the main diagonal of the matrix consists solely of zeros. Furthermore, there are exactly KK ones below the main diagonal.

Consecutive test cases are separated by newlines for readability.

Output Format

For each test case, the number of routing schemes such that every edge is traversed exactly once, modulo 109+710^9+7. It is guaranteed that there is at least one valid routing scheme for each test case.

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

For the first test case, the edges 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 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:

  • 1451 \to 4 \to 5
  • 2472 \to 4 \to 7
  • 3463 \to 4 \to 6
  • 810128 \to 10 \to 12
  • 910119 \to 10 \to 11

In general, senders {1,2,3}\{1,2,3\} can route to some permutation of receivers {5,6,7}\{5,6,7\} and senders {8,9}\{8,9\} can route to some permutation of receivers {11,12}\{11,12\}, giving an answer of 6×2=126 \times 2=12

2

5 1
SS.RR
00101
00100
10010
00000
00000

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

For the first test case, the edges are 13,15,23,31,341 \to 3,1 \to 5,2 \to 3,3 \to 1,3 \to 4

There are three possible routing schemes:

  • 1315,2341 \to 3 \to 1 \to 5,2 \to 3 \to 4
  • 134,23151 \to 3 \to 4,2 \to 3 \to 1 \to 5
  • 15,231341 \to 5,2 \to 3 \to 1 \to 3 \to 4

For the second test case, the edges are 13,24,32,36,45,531 \to 3,2 \to 4,3 \to 2,3 \to 6,4 \to 5,5 \to 3

There is only one possible routing scheme: 13245361 \to 3 \to 2 \to 4 \to 5 \to 3 \to 6

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

Some additional small test cases.

Scoring

  • Test cases 4-5 satisfy N6N \leqslant 6.
  • Test cases 6-7 satisfy K=0K=0.
  • Test cases 8-12 satisfy K=1K=1.
  • Test cases 13-24 satisfy K=2K=2.

Problem credits

Benjamin Qi