우주선

Bessie라는 소가 외계인에게 납치되어 우주선 안에 갇혔다. 우주선에는 $N$ $(1\le N\le 60)$개의 방이 있고 방 번호는 $1\ldots N$이다. 방과 방 사이에는 한 방향으로만 통하는 문이 일부 있으며, 같은 출발 방과 도착 방을 잇는 문은 둘 이상 없다. 문이 방에서 자기 자신으로 돌아오는 것도 가능하다. Bessie에게는 번호가 $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)$를 고른다. Bessie는 방 $s$에서 출발하며 곧바로 버튼 $b_s$를 누른다. 이후 아래 규칙에 따라 버튼을 누르며 우주선을 돌아다닌다. 각 방에서는 버튼을 정확히 하나 누른 뒤, 문을 통해 다른 방(같은 방도 가능)으로 나가거나 멈춰야 한다. 한 번 누른 버튼은 그 뒤에 더 큰 번호의 버튼을 누른 적이 없다면 다시 누를 수 없다. 버튼 $x$를 누르면 $x$는 사용할 수 없게 되고, 번호가 $x$보다 작은 버튼은 모두 다시 사용할 수 있게 된다. 사용할 수 없는 버튼을 누르면 Bessie는 실패하고 외계인에게 붙잡힌다. Bessie는 방 $t$에서 멈추고, 마지막으로 누른 버튼이 $b_t$이며, 사용할 수 없는 버튼을 한 번도 누르지 않았을 때만 풀려난다. $Q$ $(1\le Q\le 60)$개의 질의가 주어진다. 각 질의는 $s$, $t$, $b_s$, $b_t$의 조합이며, 각 질의마다 Bessie가 풀려나게 되는 방 이동과 버튼 누름 순서의 수를 $10^9+7$로 나눈 나머지로 구하라.

첫 줄에 $N$, $K$, $Q$가 주어진다. 이어지는 $N$개 줄에는 각각 $N$개의 비트(0 또는 1)가 주어진다. $i$번째 줄의 $j$번째 비트가 1이면 방 $i$에서 방 $j$로 가는 문이 있고, 0이면 없다. 그 다음 $Q$개 줄에 각각 정수 네 개 $b_s$, $s$, $b_t$, $t$가 주어진다.

각 질의의 답을 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.