Корова Беси похищена инопланетянами и сейчас находится внутри их корабля.
В корабле \(N\) \((1\le N\le 60)\) комнат, помеченных \(1\ldots N\). Каждые две комнаты
соединяет одна дверь. Может быть также дверь, которая ведёт из комнаты в неё же саму.
Однако никакие две двери не имеют общими начальную и конечную комнаты.
У Беси есть пульт с клавишами пронумерованными \(1\ldots K\) \((1 \le K \le 60)\).
Инопланетяне отпустят Беси, если она сможет выполнить странное задание.
Сначала они выбирают две комнаты, \(s\) и \(t\) \((1 \le s, t \le N)\), и два числа
\(b_s\) и \(b_t\) \((1 \le b_s, b_t \le K)\). Они помещают Беси в комнату \(s\) и сразу
нажимают клавишу \(b_s\). Затем Беси продолжает навигацию по кораблю, нажимая
клавиши на пульте. Имеется несколько правил, которым Беси должна следовать:
- В каждой комнате после нажатия ровно одной клавиши, она должна выбрать
или выйти через дверь в другую комнату (возможно ту же самую) или остановиться.
- Когда Беси нажимает клавишу, она больше не может нажать ту же клавишу опять,
пока не нажмёт клавишу с бОльшим номером. Другими словами, нажатие клавиши с
номером \(x\) делает эту клавишу недоступной для использования, пока все клавиши
с номерами \(<x\) будут сброшены и опять доступны для использования.
- Если Беси нажмёт неверно клавишу, она останется у инопланетян.
Беси догадалась, что только если она остановится в комнате \(t\),
последняя клавиша, которую она нажала, была \(b_t\) и она не нажала неверных клавиш.
Беси беспокоится, что не сможет выполнить задание.
Для \(Q\) \((1\le Q\le 60)\) запросов, каждый из которых состоит из выбора Беси
\(s, t, b_s\), \(b_t\), Беси хочет узнать количество последовательностей
комнат и нажатых клавиш, которые приведут к её освобождению. Выведите свой ответ
по модулю \(10^9 + 7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N,K,Q\).
Каждая их последующих \(N\) строк содержит \(N\) битов (каждый 0 или 1).
\(j\)-ое число в \(i\)-ой строке равно 1 если существует дверь из комнаты \(i\) в комнату \(j\),
и 0, если такой двери не существует.
Далее следует \(Q\) строк, каждая содержит четыре целых числа \(b_s\), \(s\), \(b_t\),
\(t\), обозначающих стартовую клавишу, стартовую комнату, финальную клавишу, финальную комнату, соответственно.
ФОРМАТ ВЫВОДА (на экран / stdout):
Количество последовательностей для каждого из \(Q\) запросов по модулю \(10^9+7\)
на отдельных строках.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|