Космический корабль
Корова Бесси была похищена инопланетянами и теперь заперта внутри инопланетного космического корабля! На космическом корабле есть 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)