Корова Бесі викрадена інопланетянами і зараз перебуває всередині їхнього корабля. У кораблі \(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\).

Формат вхідних даних

Перший рядок містить \(N,K,Q\).

Кожна з наступних \(N\) рядків містить \(N\) бітів (кожен 0 або 1). \(j\)-е число в \(i\)-му рядку дорівнює 1 якщо існує двері з кімнати \(i\) в кімнату \(j\), і 0, якщо таких дверей немає.

Далі слідує \(Q\) рядків, кожен містить чотири цілих числа \(b_s\), \(s\), \(b_t\), \(t\), що позначають стартову клавішу, стартову кімнату, фінальну клавішу, фінальну кімнату, відповідно.

Формат вихідних даних

Кількість послідовностей для кожного з \(Q\) запитів по модулю \(10^9+7\) в окремих рядках.

Приклад вхідних даних

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

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

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

Для другого запиту відповідь 0, тому що немає способу потрапити до кімнати 1 із кімнати 3.

Для третього запиту єдина можливість для Бесі перейти з кімнати 1 до кімнати 2, потім до кімнати 3, натискаючи клавіші 1 2 3.

Для 4-го запиту є 3 можливі послідовності дій Бесі:

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

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

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

Приклад вхідних даних

6 4 6
001100
001110
101101
010111
110111
000111
3 2 4 3
3 1 4 4
3 4 4 1
3 3 4 3
3 6 4 3
3 1 4 2

Приклад вихідних даних

26
49
29
27
18
22

Приклад вхідних даних

6 10 5
110101
011001
001111
101111
111010
000001
2 5 2 5
6 1 5 2
3 4 8 3
9 3 3 5
5 1 3 4

Приклад вихідних даних

713313311
716721076
782223918
335511486
539247783

Не забудьте вводити відповідь за модулем \(10^9+7\).

ОЦІНЮВАННЯ:

• У тестах 4-7 \(K\le 5\) \((b_s,s)\) одне й те саме для всіх запитів.
• У тестах 8-11 \(b_s=K-1\) та \(b_t=K\) для кожного запиту.
• У тестах 12-15 \(N,K,Q\le 20\).
• У тестах 16-23 немає додаткових обмежень.