A975 | Spaceship--Platinum

Bessie the cow has been abducted by aliens and is now trapped inside an alien
spaceship! The spaceship has $N$ $(1\le N\le 60)$ rooms labeled $1\ldots N$,
with one-way doors connecting between some pairs of rooms (due to the strange
alien technology at play, it is even possible for a door to lead from a room
back to itself!). However, no two doors share the same starting and end room.
Additionally, Bessie has a remote with buttons numbered $1\ldots K$ $(1 \le K
\le 60)$.
The aliens will release Bessie if she can complete a strange task. First, they
will choose two rooms, $s$ and $t$ $(1 \le s, t \le N)$, and two numbers,
$b_s$ and $b_t$ $(1 \le b_s, b_t \le K)$. They will start Bessie in room $s$
and immediately have her press button $b_s$. Bessie will then proceed to
navigate the ship while pressing buttons. There are a few rules for what
Bessie can do:
* In each room, after pressing exactly one button, she must choose to either exit through a door to another (possibly the same) room or stop.
* Once Bessie presses a button, it is invalid for her to press the same button again unless, in the time between uses, she has pressed a button with a higher number. In other words, pressing button number $x$ will make it unavailable for use, while all buttons with numbers $<x$ will be reset and again available for use.
* If Bessie presses an invalid button, she automatically fails and the aliens will keep her.
Bessie is released only if she stops in room $t$, the last button she pressed
was $b_t$, and no invalid buttons were ever pressed.
Bessie is worried that she may not be able to complete the task. For $Q$
$(1\le Q\le 60)$ queries, each consisting of what Bessie considers a likely
choice of $s, t, b_s$, and $b_t$, Bessie wants to know the number of sequences
of rooms and button presses that would lead to her release. Report your
answers modulo $10^9 + 7$ as they may be very large.

The first line contains $N,K,Q$.
The next $N$ lines each contain $N$ bits (each 0 or 1). The $j$-th entry of
the $i$-th line is 1 if there exists a door from room $i$ to room $j$, and 0
if no such door exists.
This is followed by $Q$ lines, each containing four integers $b_s$, $s$,
$b_t$, $t$, denoting the starting button, starting room, final button, and
final room respectively.

The number of sequences for each of the $Q$ queries modulo $10^9+7$ on
separate lines.