Tàu vũ trụ

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 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 \leq K \leq 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 \leq s, t \leq N$ ), và hai số $b_{s}$ và $b_{t}$ ( $1 \leq b_{s}, b_{t} \leq 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 \leq Q \leq 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 \leq N \leq 60$
$1 \leq K \leq 60$
$1 \leq Q \leq 60$
$1 \leq b_{s}, b_{t} \leq K$
$1 \leq s, t \leq N$

Ví dụ

Input	Output	Giải thích
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	Các cánh cửa nối phòng $1 \to 2$ , $2 \to 3$ , $3 \to 4$ , $4 \to 5$ , $6 \to 6$ . Với truy vấn 4, Bessie phải di chuyển $1 \to 2 \to 3 \to 4 \to 5$ và có 3 chuỗi nhấn nút: $(1, 2, 3, 2, 1)$ , $(1, 2, 1, 3, 1)$ , $(1, 3, 1, 2, 1)$ .
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	Đồ thị có nhiều cạnh hơn, mỗi truy vấn đều bắt đầu bằng nút 3 và kết thúc bằng nút 4.

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)$ .

Bình luận

Không có bình luận tại thời điểm này.