Космічний корабель#10374

Космічний корабель

3 секунди

128 мегабайтів

Дуже складна

Корова Бессі була викрадена інопланетянами і тепер замкнена всередині інопланетного космічного корабля! На кораблі є $n$ кімнат, пронумерованих від $1$ до $n$ , з односторонніми дверима, що з'єднують деякі пари кімнат (через незвичну інопланетну технологію можливо, що двері ведуть з кімнати назад у цю ж саму кімнату). Водночас, жодні двоє дверей не з'єднують однакову початкову і кінцеву кімнату. Також у Бессі є пульт із кнопками, пронумерованими від $1$ до $k$ .

Прибульці відпустять Бессі, якщо вона виконає незвичне завдання. Спочатку вони оберуть дві кімнати $s$ і $t$ , а також два числа $b_{s}$ b_s та $b_{t}$ b_t ( $1 \leq b_{s}, b_{t} \leq k$ 1 \leq b_s, b_t \leq k). Бессі почне у кімнаті $s$ і відразу натисне кнопку $b_{s}$ b_s. Далі Бессі буде переходити між кімнатами та натискати кнопки за такими правилами:

- У кожній кімнаті, після натискання рівно однієї кнопки, вона має або пройти через двері в іншу (можливо, ту ж саму) кімнату, або зупинитися. - Повторно натискати ту ж саму кнопку не можна, якщо між цим вона не натискала кнопку з більшим номером. Тобто, натискання кнопки номер $x$ робить її недоступною до повторного використання, водночас всі кнопки з номерами менше $x$ знову доступні. - Якщо Бессі натисне недопустиму кнопку, вона одразу програє, і інопланетяни не випустять її.

Бессі буде вільна лише тоді, якщо вона зупиниться у кімнаті $t$ , остання натиснута кнопка буде $b_{t}$ b_t, і жодна заборонена кнопка не буде натиснута.

Бессі хвилюється, що не зможе виконати завдання. Для $q$ запитів, кожен із яких містить варіанти $s$ , $t$ , $b_{s}$ b_s та $b_{t}$ b_t, Бессі хоче дізнатися, скільки існує послідовностей переходів між кімнатами й натискань кнопок, що призводять до її звільнення. Відповіді виводьте по модулю $1 0^{9} + 7$ 10^9 + 7, оскільки вони можуть бути дуже великими.

Вхідні дані

Перший рядок містить числа $n$ ( $1 \leq n \leq 60$ 1 \leq n \leq 60), $k$ ( $1 \leq k \leq 60$ 1 \leq k \leq 60), $q$ ( $1 \leq q \leq 60$ 1 \leq q \leq 60).

Далі йде $n$ рядків по $n$ символів ( $0$ або $1$ кожен). $j$ -ий символ $i$ -го рядка дорівнює $1$ , якщо існує двері з кімнати $i$ в кімнату $j$ , і $0$ , якщо такої двері немає.

Далі слідують $q$ рядків, кожен з яких містить чотири цілих числа: $b_{s}$ b_s, $s$ , $b_{t}$ b_t, $t$ ( $1 \leq s, t \leq n$ 1 \leq s, t \leq n) — стартова кнопка, стартова кімната, остання кнопка і остання кімната відповідно.

Вихідні дані

Для кожного з $q$ запитів виведіть кількість можливих послідовностей за модулем $1 0^{9} + 7$ 10^9 + 7 у окремому рядку.

Приклади

Двері з'єднують кімнати $1 \to 2$ 1 \to 2, $2 \to 3$ 2 \to 3, $3 \to 4$ 3 \to 4, $4 \to 5$ 4 \to 5 і $6 \to 6$ 6 \to 6.

Для першого запиту Бессі має зупинитися одразу після натискання першої кнопки.

Для другого запиту відповідь — нуль, бо з кімнати $3$ потрапити в кімнату $1$ неможливо.

У третьому запиті Бессі може лише перейти з кімнати $1$ у кімнату $2$ , а потім — у кімнату $3$ , натискаючи кнопки $1$ , $2$ , $3$ .

Для четвертого запиту шлях руху Бессі задано однозначно, і є три варіанти натискання кнопок:

(1, 2, 3, 2, 1) (1, 2, 1, 3, 1) (1, 3, 1, 2, 1)

(1, 2, 3, 2, 1) \\ (1, 2, 1, 3, 1) \\ (1, 3, 1, 2, 1)

Для останнього запиту є п'ять можливих варіантів натискання:

(2) (2, 3, 2) (2, 3, 1, 2) (2, 1, 3, 2) (2, 1, 3, 1, 2)

(2) \\ (2, 3, 2) \\ (2, 3, 1, 2) \\ (2, 1, 3, 2) \\ (2, 1, 3, 1, 2)

Приклад 1

Приклад 2