Bò Bessie bị người ngoài hành tinh bắt cóc và đang mắc kẹt trong một tàu vũ trụ! Tàu có \(N\) phòng được đánh số \(1\ldots N\) (\(1\le N\le 60\)), với các cửa một chiều nối một số cặp phòng. Do công nghệ kỳ lạ của người ngoài hành tinh, một cửa thậm chí có thể dẫn từ một phòng trở lại chính phòng đó. Không có hai cửa nào có cùng phòng đầu và phòng cuối. Bessie còn có một điều khiển từ xa với các nút được đánh số \(1\ldots K\) (\(1\le K\le 60\)).

Người ngoài hành tinh sẽ thả Bessie nếu cô hoàn thành một nhiệm vụ. Đầu tiên, họ chọn hai phòng \(s\) và \(t\) (\(1\le s,t\le N\)), cùng hai số \(b_s\) và \(b_t\) (\(1\le b_s,b_t\le K\)). Họ đặt Bessie vào phòng \(s\) và yêu cầu cô lập tức nhấn nút \(b_s\). Sau đó, Bessie di chuyển trong tàu và nhấn các nút theo những quy tắc sau:

• Trong mỗi phòng, sau khi nhấn đúng một nút, cô phải chọn đi qua một cửa đến một phòng khác, có thể là chính phòng hiện tại, hoặc dừng lại.
• Sau khi Bessie nhấn một nút, cô không được nhấn lại nút đó trừ khi giữa hai lần sử dụng, cô đã nhấn một nút có số lớn hơn. Nói cách khác, nhấn nút số \(x\) làm nút đó không thể sử dụng, đồng thời đặt lại và cho phép sử dụng tất cả các nút có số \(<x\).
• Nếu Bessie nhấn một nút không hợp lệ, cô lập tức thất bại và bị giữ lại.
• Bessie chỉ được thả nếu cô dừng tại phòng \(t\), nút cuối cùng đã nhấn là \(b_t\), và cô chưa từng nhấn nút không hợp lệ.

Bessie lo rằng mình có thể không hoàn thành được nhiệm vụ. Với \(Q\) truy vấn (\(1\le Q\le 60\)), mỗi truy vấn là một lựa chọn có thể xảy ra của \(s\), \(t\), \(b_s\) và \(b_t\), hãy tính số dãy phòng và lần nhấn nút giúp Bessie được thả. Vì đáp án có thể rất lớn, hãy lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(K\) và \(Q\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) bit, mỗi bit là 0 hoặc 1. Phần tử thứ \(j\) của dòng thứ \(i\) bằng 1 nếu có cửa từ phòng \(i\) đến phòng \(j\), và bằng 0 nếu không có.

Tiếp theo là \(Q\) dòng, mỗi dòng chứa bốn số nguyên \(b_s\), \(s\), \(b_t\), \(t\), lần lượt biểu thị nút xuất phát, phòng xuất phát, nút cuối cùng và phòng cuối cùng.

Dữ liệu ra

Với mỗi truy vấn trong \(Q\) truy vấn, in trên một dòng riêng số dãy hợp lệ, lấy modulo \(10^9+7\).

Phân nhóm

• Trong các test 4-7, \(K\le 5\) và \((b_s,s)\) giống nhau trong mọi truy vấn.
• Trong các test 8-11, \(b_s=K-1\) và \(b_t=K\) với mọi truy vấn.
• Trong các test 12-15, \(N,K,Q\le 20\).
• Trong các test 16-23, không có ràng buộc bổ sung.

Ví dụ

6 3 8
010000
001000
000100
000010
000000
000001
1 1 1 1
3 3 1 1
1 1 3 3
1 1 1 5
2 1 1 5
1 1 2 5
3 1 3 5
2 6 2 6

1
0
1
3
2
2
0
5

6 4 6
001100
001110
101101
010111
110111
000111
3 2 4 3
3 1 4 4
3 4 4 1
3 3 4 3
3 6 4 3
3 1 4 2

26
49
29
27
18
22

6 10 5
110101
011001
001111
101111
111010
000001
2 5 2 5
6 1 5 2
3 4 8 3
9 3 3 5
5 1 3 4

713313311
716721076
782223918
335511486
539247783

Nguồn

USACO 2020 December Contest, Platinum - Spaceship: https://usaco.org/index.php?page=viewproblem2&cpid=1069

Tác giả: Benjamin Qi.