33OJ
登录 注册

#P17702. [ICPC 2019 Nanjing R] Holes

    ID: 20154 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>递推2019概率论期望高斯消元ICPC南京

[ICPC 2019 Nanjing R] Holes

Problem Description

Given an n×nn \times n chessboard, the rows and columns are numbered from 11 to nn respectively. RDC, a handsome juvenile, punched several holes in specified locations, the ii-th of which locates at (xi,yi)(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)(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.

Input Format

The first line contains an integer TT (1≤T≤201 \leq T \leq 20), indicating the number of test cases.

For each test case, the first line contains two integers nn and kk (2≤n≤200,1≤k≤2002 \leq n \leq 200, 1 \leq k \leq 200) indicating the size of the given chessboard and the number of holes. Then kk lines follow, the ii-th of which contains two integers xix_i and yiy_i (1≤xi,yi≤n1 \leq x_i, y_i \leq n) indicating the location of the ii-th hole. The last line of each test case contains two integers rr and cc (1≤r,c≤n1 \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\max(n, k) > 5 hold in at most one test case.

Output Format

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 pq\frac{p}{q}, you should output the minimum non-negative integer rr such that q⋅r≡p(mod109+7)q \cdot r \equiv p \pmod{10^9+7}. You may safely assume that such rr always exists in all test cases. If a hole is unreachable, output GG 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