시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 0 0 0 0.000%

문제

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

Little Q also has a pet dog. Now, the dog is getting lost on the chessboard at the cell $(r_0, c_0)$. It will move to a random adjacent cell every second. Each of the adjacent cells is selected with equal probability. Here, two cells are adjacent if they share a common edge. If the dog arrives at a cell with a punched hole, it will fall into the hole.

Now, Little Q is wondering: for each hole, what is the expected number of seconds that the pet walks on the chessboard, 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$) indicating the size of the given chessboard and the number of holes.

Then $k$ lines follow, the $i$-th of which contains two integers $r_i$ and $c_i$ ($1 \leq r_i, c_i \leq n$) indicating 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$) denoting the starting location of the pet.

It is guaranteed that all given holes are distinct, and the pet is not located at a hole initially. It is also guaranteed that $\max(n, k) > 5$ holds in at most one test case.

출력

For each test case, output a single line with $k$ integers: for each hole, in the order they are given in the input, print the expected number of seconds the pet walks on the chessboard, given that it finally falls into this hole.

More precisely, if a hole is reachable and the reduced fraction of the expected number of seconds 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 "-1" instead.

예제 입력 1

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

예제 출력 1

-1 4 4
669185882 381533358 341349117