P7155 [USACO20DEC] Spaceship P

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 $

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.

For each of the $Q$ queries, output on its own line the number of valid action sequences modulo $10^9+7$.

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