The Missing Pet

You are given an $n \times n$ chessboard, with rows and columns numbered from 1 to $n$. Little Q punched several holes in specified locations: the $i$-th hole is at $(r_i, c_i)$.

Little Q also has a pet dog. The dog gets lost on the board at cell $(r_0, c_0)$. Every second, it moves to a random adjacent cell, and each adjacent cell is chosen with equal probability. Two cells are adjacent if they share an edge. If the dog arrives at a cell with a punched hole, it falls into the hole.

For each hole, what is the expected number of seconds the dog walks on the board, given that it finally falls into this hole? Please help him.

The first line contains an integer $T$ ($1 \leq T \leq 20$), the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 200$, $1 \leq k \leq 200$), the size of the chessboard and the number of holes.

Then $k$ lines follow. The $i$-th of them contains two integers $r_i$ and $c_i$ ($1 \leq r_i, c_i \leq n$), the location of the $i$-th hole.

The last line of each test case contains two integers $r_0$ and $c_0$ ($1 \leq r_0, c_0 \leq n$), the starting location of the pet.

All holes are distinct, and the pet does not start on a hole. It is guaranteed that $\max(n, k) > 5$ holds in at most one test case.

For each test case, output a single line with $k$ integers: one per hole, in input order, the expected number of seconds the pet walks before falling into that hole, given that it falls into it. If a hole cannot be reached, print -1 instead.

If a hole is reachable and the reduced fraction of the expected value is $\frac{p}{q}$, print the minimum non-negative integer $r$ such that $q \cdot r \equiv p \pmod{10^9+7}$. You may assume such $r$ always exists.