사라진 애완견

$n \times n$ 크기의 체스판이 있다. 행과 열은 각각 1부터 $n$까지 번호가 매겨져 있다. 리틀 Q가 지정한 위치 여러 곳에 구멍을 뚫었다. $i$번째 구멍은 $(r_i, c_i)$에 있다.

리틀 Q에게는 반려견이 한 마리 있다. 이 개는 $(r_0, c_0)$ 칸에서 길을 잃었다. 개는 1초마다 인접한 칸 중 하나로 옮겨 간다. 인접한 칸은 각각 같은 확률로 선택된다. 두 칸이 변을 공유하면 인접한 칸이다. 개가 구멍이 뚫린 칸에 도착하면 그 구멍에 빠진다.

각 구멍에 대해, 개가 결국 그 구멍에 빠졌다는 조건에서 개가 체스판 위를 돌아다니는 시간의 기댓값은 몇 초인가? 리틀 Q를 도와 구해 달라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \leq T \leq 20$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 체스판의 크기 $n$과 구멍의 개수 $k$가 주어진다 ($2 \leq n \leq 200$, $1 \leq k \leq 200$).

이어서 $k$개의 줄이 주어진다. $i$번째 줄에는 $i$번째 구멍의 위치 $r_i$와 $c_i$가 주어진다 ($1 \leq r_i, c_i \leq n$).

각 테스트 케이스의 마지막 줄에는 개의 출발 위치 $r_0$과 $c_0$이 주어진다 ($1 \leq r_0, c_0 \leq n$).

모든 구멍은 서로 다르며, 개는 처음에 구멍 위에 있지 않다. $\max(n, k) > 5$를 만족하는 테스트 케이스는 최대 하나이다.

각 테스트 케이스에 대해 $k$개의 정수를 한 줄에 출력한다. 각 구멍에 대해 입력 순서대로, 개가 그 구멍에 빠졌다는 조건에서 개가 빠지기 전까지 걸은 시간의 기댓값을 출력한다. 도달할 수 없는 구멍에는 -1을 출력한다.

구멍에 도달할 수 있고 기댓값의 기약분수가 $\frac{p}{q}$이면, $q \cdot r \equiv p \pmod{10^9+7}$을 만족하는 가장 작은 음이 아닌 정수 $r$을 출력한다. 그러한 $r$은 항상 존재한다고 가정해도 된다.