Tàu vũ trụ

Bessie đã bị người ngoài hành tinh bắt cóc và hiện đang bị nhốt bên trong một tàu vũ trụ! Con tàu có $N$ ($1\le N\le 60$) phòng được đánh số $1\dots N$, với các cánh cửa một chiều nối giữa một số cặp phòng (do công nghệ ngoài hành tinh kỳ lạ, thậm chí có thể có cánh cửa dẫn từ một phòng trở lại chính nó!). Tuy nhiên, không có hai cánh cửa nào có cùng phòng xuất phát và phòng kết thúc. Ngoài ra, Bessie có một chiếc điều khiển với các nút được đánh số $1\dots 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ụ kỳ lạ. Đầu tiên, họ sẽ chọn hai phòng $s$ và $t$ ($1\le s,t\le N$), và hai số $b_s$ và $b_t$ ($1\le b_s,b_t\le K$). Họ sẽ đặt Bessie vào phòng $s$ và ngay lập tức yêu cầu cô nhấn nút $b_s$. Sau đó Bessie sẽ di chuyển quanh tàu trong khi nhấn các nút. Có một số quy tắc cho những gì Bessie có thể làm:

• Ở mỗi phòng, sau khi nhấn đúng một nút, cô phải chọn hoặc đi qua một cánh cửa đến phòng khác (có thể là cùng phòng) hoặc dừng lại.
• Sau khi Bessie nhấn một nút, nút đó sẽ không thể dùng lại trừ khi trong khoảng thời gian đó cô đã nhấn một nút có số cao hơn. Nói cách khác, nhấn nút số $x$ sẽ làm nút đó không khả dụng, trong khi tất cả các nút có số $<x$ sẽ được đặt lại và có thể sử dụng lại.
• Nếu Bessie nhấn một nút không hợp lệ, cô tự động thất bại và người ngoài hành tinh sẽ giữ cô lại.

Bessie chỉ được thả khi cô dừng lại ở phòng $t$, nút cuối cùng cô nhấn là $b_t$, và không có nút không hợp lệ nào được nhấn.

Bessie lo lắng rằng mình có thể không hoàn thành được nhiệm vụ. Với $Q$ ($1\le Q\le 60$) truy vấn, mỗi truy vấn gồm một lựa chọn $s,t,b_s$ và $b_t$ mà Bessie cho là có khả năng xảy ra, Bessie muốn biết số chuỗi phòng và lần nhấn nút sẽ dẫn đến việc cô được thả. Báo cáo câu trả lời của bạn theo modulo ${10}^9+7$ vì chúng có thể rất lớn.

Dữ liệu vào

Dòng đầu tiên chứa $N,K,Q$.

• $N$ dòng tiếp theo, mỗi dòng chứa $N$ bit (0 hoặc 1). Bit thứ $j$ của dòng thứ $i$ là 1 nếu tồn tại cánh cửa từ phòng $i$ đến phòng $j$, và 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 là nút bắt đầu, phòng bắt đầu, nút kết thúc và phòng kết thúc.

Dữ liệu ra

Số chuỗi cho mỗi trong số $Q$ truy vấn theo modulo ${10}^9+7$, mỗi truy vấn trên một dòng riêng.

Ràng buộc

• $1\le N\le 60$
• $1\le K\le 60$
• $1\le Q\le 60$
• $1\le b_s,b_t\le K$
• $1\le s,t\le N$

Ví dụ

Ghi chú

Với truy vấn cuối cùng của ví dụ 1 ($b_s=2$, $s=6$, $b_t=2$, $t=6$), Bessie có 5 chuỗi nhấn nút có thể: $(2)$, $(2,3,2)$, $(2,3,1,2)$, $(2,1,3,2)$, $(2,1,3,1,2)$.