Ski Routes

A mountainous region is described by a grid of numbers with $N$ rows and $M$ columns, where each entry is the terrain height at that grid point. To serve skiers, $K$ ski lifts have been built between selected pairs of points. Every lift works in one direction only, carrying a skier from a lower point up to a higher point.

A ski route consists of a non-empty sequence of lift rides, during which the skier's height keeps increasing, followed by a sequence of descents that returns to the point where the route began. Consecutive lift rides must connect: each ride starts at the point where the previous one ended. Each descent is a single move to an orthogonally adjacent cell (one of the four directions), and every descent must go from a higher cell to a strictly lower one.

The resorts want to advertise the slogan: "We have $X$ ski routes." Given the list of lifts and the height of every point, compute $X$ modulo $10^9 + 7$.

The first line contains an integer $Z$ ($1 \le Z \le 10$), the number of test cases. The test cases follow.

The first line of each test case contains two space-separated integers $N$ and $M$ ($1 \le N, M \le 100$). The next $N$ lines describe the height table row by row, from row $1$ to row $N$; each of these lines contains $M$ integers $h$ ($0 \le h \le 10^9$), listed from column $1$ to column $M$.

The next line contains an integer $K$ ($1 \le K \le 300$), the number of lifts. Each of the following $K$ lines contains four integers $w_0\ c_0\ w_1\ c_1$, describing a lift from point $(w_0, c_0)$ to point $(w_1, c_1)$. Rows are numbered from $1$ to $N$ and columns from $1$ to $M$. Every lift ends strictly higher than it starts. Several lifts may connect the same pair of points.

For each test case, print on a separate line the number of ski routes modulo $10^9 + 7$.

Here $(r, c)$ denotes the cell in row $r$ and column $c$.

For the first sample, the possible routes are:

• $(1,1) \to (1,2) \to (1,1)$
• $(1,1) \to (1,2) \to (2,2) \to (1,2) \to (1,1)$
• $(1,1) \to (1,2) \to (2,2) \to (2,1) \to (1,1)$
• $(1,1) \to (2,1) \to (1,1)$
• $(1,2) \to (2,2) \to (1,2)$

The second sample shows that several lifts may connect the same two points.