P17702 [ICPC 2019 Nanjing R] Holes

Given an $n \times n$ chessboard, the rows and columns are numbered from $1$ to $n$ respectively. RDC, a handsome juvenile, punched several holes in specified locations, the $i$-th of which locates at $(x_i, y_i)$. RDC also has a pet Pork Ribs dragon whose name is PRD. Now, PRD is drunk and was left on the chessboard at the cell $(r, c)$. It will walk randomly and move to an adjacent cell every second with equal probability. Here two cells are adjacent if they share a common edge. PRD will fall into the hole and start to sleep when it arrives at a cell with a punched hole. Now, RDC wonders the expected time consumption of his pet for each hole that his pet will finally stay in.

The first line contains an integer $T$ ($1 \leq T \leq 20$), indicating 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$) indicating the size of the given chessboard and the number of holes. Then $k$ lines follow, the $i$-th of which contains two integers $x_i$ and $y_i$ ($1 \leq x_i, y_i \leq n$) indicating the location of the $i$-th hole. The last line of each test case contains two integers $r$ and $c$ ($1 \leq r, c \leq n$) described as above. We guarantee that PRD is not locating at a hole initially, and all given holes are distinct. We also guarantees that $\max(n, k) > 5$ hold in at most one test case.

For each test case, output the expected time consumption (in seconds) for each hole in order in a single line. More precisely, if a hole is reachable and the reduced fraction of the expected time consumption is $\frac{p}{q}$, you should output the minimum non-negative integer $r$ such that $q \cdot r \equiv p \pmod{10^9+7}$. You may safely assume that such $r$ always exists in all test cases. If a hole is unreachable, output `GG` at the right place.