Xét một mạng gồm \(N\) nút (\(2\le N\le100\)) được đánh số \(1\ldots N\). Mỗi nút được chỉ định là nút gửi, nút nhận hoặc không thuộc loại nào. Số nút gửi là \(S\), bằng số nút nhận, và \(S\ge1\).

Các liên kết giữa những nút trong mạng được mô tả bằng một danh sách cạnh có hướng, mỗi cạnh có dạng \(i\to j\), nghĩa là nút \(i\) có thể định tuyến đến nút \(j\). Tất cả các cạnh này đều thỏa mãn \(i<j\), ngoại trừ \(K\) cạnh thỏa mãn \(i>j\) (\(0\le K\le2\)). Không có khuyên, tức cạnh dạng \(i\to i\).

Một “phương án định tuyến” là một tập gồm \(S\) đường đi có hướng từ các nút gửi đến các nút nhận sao cho không có hai đường đi nào chung đầu mút. Nói cách khác, các đường đi nối các nút gửi phân biệt tới các nút nhận phân biệt. Một đường đi từ nút gửi \(s\) đến nút nhận \(r\) có thể được mô tả bằng dãy nút

sao cho cạnh có hướng \(v_i\to v_{i+1}\) tồn tại với mọi \(0\le i<e\). Một nút có thể xuất hiện nhiều lần trong cùng một đường đi.

Hãy đếm số phương án định tuyến phân biệt sao cho mỗi cạnh có hướng được đi qua đúng một lần. Vì kết quả có thể rất lớn, hãy in phần dư theo \(10^9+7\). Dữ liệu bảo đảm có ít nhất một phương án thỏa mãn các điều kiện này.

Mỗi dữ liệu vào chứa \(T\) bộ test (\(1\le T\le20\)) cần được giải độc lập. Tổng \(N^2\) trên mọi bộ test không vượt quá \(2\cdot10^4\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số bộ test.

Dòng đầu tiên của mỗi bộ test chứa \(N\) và \(K\). Lưu ý rằng \(S\) không được cho trực tiếp trong dữ liệu vào.

Dòng thứ hai của mỗi bộ test chứa một xâu độ dài \(N\). Ký tự thứ \(i\) của xâu là S nếu nút thứ \(i\) là nút gửi, R nếu nút thứ \(i\) là nút nhận, và . nếu nút thứ \(i\) không thuộc loại nào. Số ký tự R bằng số ký tự S, và có ít nhất một ký tự S.

\(N\) dòng tiếp theo của mỗi bộ test, mỗi dòng chứa một xâu bit gồm \(N\) chữ số 0 và 1. Bit thứ \(j\) của dòng thứ \(i\) bằng \(1\) nếu có cạnh có hướng từ nút \(i\) đến nút \(j\), và bằng \(0\) nếu không có. Do không có khuyên, đường chéo chính của ma trận chỉ gồm các chữ số 0. Ngoài ra, có đúng \(K\) chữ số 1 nằm dưới đường chéo chính.

Các bộ test liên tiếp được ngăn cách bằng dòng trống cho dễ đọc.

Dữ liệu ra

Với mỗi bộ test, in số phương án định tuyến sao cho mỗi cạnh được đi qua đúng một lần, lấy phần dư theo \(10^9+7\). Dữ liệu bảo đảm mỗi bộ test có ít nhất một phương án hợp lệ.

Phân nhóm

• Các test 4-5 thỏa mãn \(N\le6\).
• Các test 6-7 thỏa mãn \(K=0\).
• Các test 8-12 thỏa mãn \(K=1\).
• Các test 13-24 thỏa mãn \(K=2\).

Ví dụ

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

Giải thích ví dụ 1. Trong bộ test đầu tiên, các cạnh là \(1\to3\), \(2\to3\), \(3\to4\), \(3\to5\), \(4\to6\), \(5\to6\), \(6\to7\), \(6\to8\). Có bốn phương án định tuyến:

• \(1\to3\to4\to6\to7, 2\to3\to5\to6\to8\)
• \(1\to3\to5\to6\to7, 2\to3\to4\to6\to8\)
• \(1\to3\to4\to6\to8, 2\to3\to5\to6\to7\)
• \(1\to3\to5\to6\to8, 2\to3\to4\to6\to7\)

Trong bộ test thứ hai, các cạnh là \(1\to4\), \(2\to4\), \(3\to4\), \(4\to5\), \(4\to6\), \(4\to7\), \(8\to10\), \(9\to10\), \(10\to11\), \(10\to12\). Một phương án có thể có các đường đi:

• \(1\to4\to5\)
• \(2\to4\to7\)
• \(3\to4\to6\)
• \(8\to10\to12\)
• \(9\to10\to11\)

Nói chung, các nút gửi \(\{1,2,3\}\) có thể định tuyến tới một hoán vị bất kỳ của các nút nhận \(\{5,6,7\}\), và các nút gửi \(\{8,9\}\) có thể định tuyến tới một hoán vị bất kỳ của các nút nhận \(\{11,12\}\), cho kết quả \(6\cdot2=12\).

Giải thích ví dụ 2. Trong bộ test đầu tiên, các cạnh là \(1\to3\), \(1\to5\), \(2\to3\), \(3\to1\), \(3\to4\). Có ba phương án định tuyến:

• \(1\to3\to1\to5\), \(2\to3\to4\)
• \(1\to3\to4\), \(2\to3\to1\to5\)
• \(1\to5\), \(2\to3\to1\to3\to4\)

Trong bộ test thứ hai, các cạnh là \(1\to3\), \(2\to4\), \(3\to2\), \(3\to6\), \(4\to5\), \(5\to3\). Chỉ có một phương án định tuyến:

\(1\to3\to2\to4\to5\to3\to6\).

Giải thích ví dụ 3. Đây là một số bộ test nhỏ bổ sung.

Nguồn

USACO 2021 US Open, Platinum - Routing Schemes: https://usaco.org/index.php?page=viewproblem2&cpid=1141

Tác giả: Benjamin Qi.