Корова Бесси была похищена инопланетянами и теперь заперта внутри инопланетного космического корабля! На космическом корабле есть n комнат, пронумерованных от 1 до n, с односторонними дверями, соединяющими некоторые пары комнат (из-за странной технологии пришельцев в игре, дверь из комнаты может даже вести обратно в нее же). Однако никакие две двери не имеют одну и ту же начальную и конечную комнаты. Кроме того, у Бесси есть пульт с кнопками, пронумерованными с 1 до k.

Пришельцы освободят Бесси, если она сможет выполнить странное задание. Сначала они выберут две комнаты s и t и два числа bs и bt (1 ≤ bs, bt ≤ k). Они запустят Бесси в комнату s и сразу же заставят ее нажать кнопку bs. Затем Бесси продолжит навигацию по кораблю, нажимая кнопки. Есть несколько правил того, что может делать Бесси:

• В каждой комнате после нажатия ровно одной кнопки она должна либо выйти через дверь в другую (возможно, ту же) комнату, либо остановиться.
• После того, как Бесси нажмет кнопку, она не может повторно нажать ту же кнопку, если в промежутке между использованиями она не нажала кнопку с большим номером. Другими словами, нажатие кнопки с номером x сделает ее недоступной для использования, а все кнопки с номерами < x будут сброшены и снова доступны для использования.
• Если Бесси нажмет неверную кнопку, она автоматически терпит неудачу, и инопланетяне не выпустят ее.

Бесси будет освобождена только в том случае, если она остановится в комнате t, последняя кнопка, которую она нажала, была bt, и никакие недопустимые кнопки никогда не нажимались.

Бесси беспокоится, что она не сможет выполнить задание. Для q запросов, каждый из которых состоит из набора s, t, bs и bt, Бесси хочет знать количество последовательностей комнат и нажатий кнопок, которые привели бы к ее освобождению. Выведите свои ответы по модулю 109 + 7, так как они могут быть очень большими.

Входные данные

Первая строка содержит числа n (1 ≤ n ≤ 60), k (1 ≤ k ≤ 60), q (1 ≤ q ≤ 60). Каждая из следующих n строк содержит n бит (каждый 0 или 1). j - ая запись в i - ой строке содержит 1, если существует дверь из комнаты i в комнату j, и 0 если такой двери нет.

Далее следуют q строк, каждая из которых содержит четыре целых числа bs, s, bt, t (1 ≤ s, t ≤ n), обозначающие стартовую кнопку, стартовую комнату, последнюю кнопку и последнюю комнату соответственно.

Выходные данные

Выведите количество последовательностей для каждого из q запросов по модулю 109 + 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)