Problem Description

The cow Bessie has been abducted by aliens and is now locked inside an alien spaceship. The spaceship has $N$ ($1\le N\le 60$) rooms, numbered $1\ldots N$. Some pairs of rooms are connected by one-way doors (because of strange alien technology, a door may even lead from a room back to itself). However, no two doors have exactly the same starting room and ending room. In addition, Bessie has a remote control with buttons numbered $1\ldots K$ ($1\le K\le 60$).

If Bessie can complete a strange task, the aliens will release her. First, they choose two rooms $s$ and $t$ ($1\le s,t\le N$), and two integers $b_s$ and $b_t$ ($1\le b_s,b_t\le K$). They place Bessie in room $s$ and make her immediately press button $b_s$. Then Bessie must continue moving around the spaceship while pressing buttons. There are some rules that Bessie's actions must follow:

• In each room, after pressing exactly one button, she must either choose a door to leave to another room (possibly returning to the same room) or stop moving.
• Once Bessie presses a button, pressing that same button again is illegal unless she has pressed a button with a larger number in between. In other words, pressing button $x$ makes this button illegal, while all buttons with numbers $<x$ are reset to legal.
• If Bessie presses an illegal button, the task immediately fails and the aliens will keep her locked up.

Bessie is released only if she stops in room $t$, the last button she pressed is $b_t$, and she has never pressed an illegal button.

Bessie worries that she might not be able to complete this task. For $Q$ ($1\le Q\le 60$) queries, each query contains a set of $s,t,b_s,$ and $b_t$ that Bessie thinks might be possible. She wants to know the number of room and button sequences that can lead to her release. Since the answer may be very large, output it modulo $10^9+7$.

Constraints

• $1\le N\le 60$.
• $1\le K\le 60$.
• $1\le Q\le 60$.

Input Format

The first line contains $N,K,Q$.

The next $N$ lines each contain $N$ binary digits ($0$ or $1$). If there is a door from room $i$ to room $j$, then the $j$-th digit of the $i$-th line is 1; otherwise it is 0.

The next $Q$ lines each contain four integers $b_s$, $s$, $b_t$, $t$, representing the starting button, starting room, ending button, and ending room.

Output Format

For each of the $Q$ queries, output on its own line the number of valid action sequences modulo $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

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

Hint

The doors connect rooms $1\to 2$, $2\to 3$, $3\to 4$, $4\to 5$, and $6\to 6$.

For the first query, Bessie must stop immediately after pressing the first button.

For the second query, the answer is clearly zero, because it is impossible to go from room 3 to room 1.

For the third query, Bessie's only choice is to move from room 1 to room 2 to room 3, while pressing buttons 1, 2, and 3.

For the fourth query, Bessie's movement is unique, and she has three possible button sequences:

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

For the last query, Bessie has five possible button sequences:

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

Test Point Properties

• In test points 4-7, $K\le 5$ and $(b_s,s)$ is the same across all queries.
• In test points 8-11, for all queries $b_s=K-1$ and $b_t=K$.
• In test points 12-15, $N,K,Q\le 20$.
• In test points 16-23, there are no additional restrictions.

Problem by: Benjamin Qi.

Translated by ChatGPT 5