Космічний корабель
Корова Бессі була викрадена інопланетянами і тепер замкнена всередині інопланетного космічного корабля! На космічному кораблі є n кімнат, пронумерованих від 1 до n, з односторонніми дверима, що з'єднують деякі пари кімнат (через дивну технологію прибульців у грі, двері з кімнати можуть навіть вести назад у неї ж). Однак жодні дві двері не мають одну й ту ж початкову та кінцеву кімнату. Крім того, у Бессі є пульт з кнопками, пронумерованими з 1 до k.
Прибульці звільнять Бессі, якщо вона зможе виконати дивне завдання. Спочатку вони виберуть дві кімнати s і t і два числа b[s] і b[t] (1 ≤ b[s], b[t] ≤ k). Вони запустять Бессі в кімнату s і відразу ж змусять її натиснути кнопку b[s]. Потім Бессі продовжить навігацію по кораблю, натискаючи кнопки. Є кілька правил того, що може робити Бессі:
У кожній кімнаті після натискання рівно однієї кнопки вона повинна або вийти через двері в іншу (можливо, ту ж саму) кімнату, або зупинитися.
Після того, як Бессі натисне кнопку, вона не може повторно натиснути ту ж кнопку, якщо в проміжку між використаннями вона не натиснула кнопку з більшим номером. Іншими словами, натискання кнопки з номером x зробить її недоступною для використання, а всі кнопки з номерами < x будуть скинуті і знову доступні для використання.
Якщо Бессі натисне неправильну кнопку, вона автоматично зазнає невдачі, і прибульці не випустять її.
Бессі буде звільнена тільки в тому випадку, якщо вона зупиниться в кімнаті t, остання кнопка, яку вона натиснула, була b[t], і жодні недопустимі кнопки ніколи не натискалися.
Бессі хвилюється, що вона не зможе виконати завдання. Для q запитів, кожен з яких складається з набору s, t, b[s] і b[t], Бессі хоче знати кількість послідовностей кімнат і натискань кнопок, які привели б до її звільнення. Виведіть свої відповіді за модулем 10^9 + 7, оскільки вони можуть бути дуже великими.
Вхідні дані
Перша рядок містить числа n (1 ≤ n ≤ 60), k (1 ≤ k ≤ 60), q (1 ≤ q ≤ 60). Кожен з наступних n рядків містить n біт (кожен 0 або 1). j-ий запис у i-му рядку містить 1, якщо існує двері з кімнати i в кімнату j, і 0 якщо такої двері немає.
Далі слідують q рядків, кожен з яких містить чотири цілі числа b[s], s, b[t], t (1 ≤ s, t ≤ n), що позначають стартову кнопку, стартову кімнату, останню кнопку і останню кімнату відповідно.
Вихідні дані
Виведіть кількість послідовностей для кожного з q запитів за модулем 10^9 + 7 в окремому рядку.
Приклад
Двері з'єднують кімнати 1 → 2, 2 → 3, 3 → 4, 4 → 5 і 6 → 6.
Для першого запиту Бессі повинна зупинитися відразу після натискання першої кнопки.
На другий запит відповідь дорівнює нулю, тому що немає можливості потрапити в кімнату 1 з кімнати 3.
Для третього запиту єдиний варіант Бессі - перейти з кімнати 1 в кімнату 2 і потім в кімнату 3, натискаючи кнопки 1, 2 і 3.
Для четвертого запиту характер руху Бессі фіксований, і у неї є три можливі послідовності натискання кнопок:
(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)