409241: GYM103466 D 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" (without quotes) at the right place.

2
3 3
1 1
1 2
2 1
2 2
5 3
5 3
4 1
3 2
4 5

GG 4 4
669185882 381533358 341349117