Sơ đồ Định Tuyến

Cho một mạng gồm $N$ nút đánh số từ $1$ đến $N$, kết nối bởi các cạnh có hướng. Mỗi nút được gán nhãn: S (nguồn), R (đích), hoặc . (trung gian). Số lượng nút nguồn bằng số lượng nút đích.

Một sơ đồ định tuyến là tập hợp các đường đi có hướng từ các nút nguồn đến các nút đích sao cho:

• Mỗi cạnh trong đồ thị được đi qua đúng một lần (bởi đúng một đường đi).
• Không có hai đường đi nào chia sẻ cùng nút đầu hoặc nút cuối.
• Không có đường đi nào tạo thành vòng lặp (chu trình).

Đồ thị được mô tả bởi ma trận kề $N\times N$ (ký tự 0/1). Mọi cạnh $i\to j$ đều thỏa mãn $i<j$, ngoại trừ đúng $K$ cạnh có $i>j$ (gọi là cạnh ngược).

Đếm số sơ đồ định tuyến hợp lệ, theo modulo ${10}^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa $T$ — số lượng test case.

Với mỗi test case:

• Dòng đầu: hai số nguyên $N$ và $K$.
• Dòng tiếp theo: xâu độ dài $N$ gồm các ký tự S, R, . mô tả loại mỗi nút.
• $N$ dòng tiếp theo: mỗi dòng là xâu nhị phân độ dài $N$, dòng $i$ mô tả các cạnh xuất phát từ nút $i$ (ký tự $j$ là 1 nếu có cạnh $i\to j$).

Dữ liệu ra

Với mỗi test case, in ra một số nguyên — số sơ đồ định tuyến hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $1\le T\le 20$
• $2\le N\le 100$
• $0\le K\le 2$ — số cạnh $i\to j$ với $i>j$
• $\sum N^2\le 2\times {10}^4$
• Luôn tồn tại ít nhất một sơ đồ định tuyến hợp lệ
• Tại mỗi nút $v$: $\text{in\_deg}(v)+[v\text{ là nguồn}]=\text{out\_deg}(v)+[v\text{ là đích}]$

Subtask:

• Test 4–5: $N\le 6$
• Test 6–7: $K=0$
• Test 8–12: $K=1$
• Test 13–24: $K=2$

Ví dụ

Ghi chú

• Cạnh ngược là cạnh $i\to j$ với $i>j$ (chỉ số nút lớn hơn đến nhỏ hơn).
• Do tất cả cạnh xuôi ($i<j$) không thể tạo chu trình trong thứ tự tô-pô, chỉ cạnh ngược mới có thể gây ra vòng lặp.