B. Baggage Claimtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputEvery airport has a baggage claim area, and Balbesovo Airport is no exception. At some point, one of the administrators at Sheremetyevo came up with an unusual idea: to change the traditional shape of the baggage claim conveyor from a carousel to a more complex form.Suppose that the baggage claim area is represented as a rectangular grid of size $$$n \times m$$$. The administration proposed that the path of the conveyor should pass through the cells $$$p_1, p_2, \ldots, p_{2k+1}$$$, where $$$p_i = (x_i, y_i)$$$.For each cell $$$p_i$$$ and the next cell $$$p_{i+1}$$$ (where $$$1 \leq i \leq 2k$$$), these cells must share a common side. Additionally, the path must be simple, meaning that for no pair of indices $$$i \neq j$$$ should the cells $$$p_i$$$ and $$$p_j$$$ coincide.Unfortunately, the route plan was accidentally spoiled by spilled coffee, and only the cells with odd indices of the path were preserved: $$$p_1, p_3, p_5, \ldots, p_{2k+1}$$$. Your task is to determine the number of ways to restore the original complete path $$$p_1, p_2, \ldots, p_{2k+1}$$$ given these $$$k+1$$$ cells.Since the answer can be very large, output it modulo $$$10^9+7$$$.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$). The description of the test cases follows. The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 1000$$$, $$$n \cdot m \ge 3$$$, $$$1 \le k \le \left\lfloor \frac12 (n m - 1) \right\rfloor$$$) — the dimensions of the grid and a parameter defining the length of the path.Next, there are $$$k+1$$$ lines, the $$$i$$$-th of which contains two integers $$$x_{2i-1}$$$ and $$$y_{2i-1}$$$ ($$$1 \le x_{2i-1} \le n$$$, $$$1 \le y_{2i-1} \le m$$$) — the coordinates of the cell $$$p_{2i-1}$$$ that lies on the path.It is guaranteed that all pairs $$$(x_{2i-1}, y_{2i-1})$$$ are distinct.It is guaranteed that the sum $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.OutputFor each test case, output a single integer — the number of ways to restore the original complete path modulo $$$10^9+7$$$.ExampleInput52 4 21 12 22 41 4 11 11 45 5 112 53 44 55 44 35 24 13 22 11 22 31 43 4 41 22 13 22 33 43 3 22 21 11 3Output2
0
2
5
1
NoteIn the first test case, there are two possible paths: $$$(1,1) \to (2,1) \to (2, 2) \to (2, 3) \to (2, 4)$$$ $$$(1,1) \to (1,2) \to (2, 2) \to (2, 3) \to (2, 4)$$$ In the second test case, there is no suitable path, as the cells $$$(1,1)$$$ and $$$(1,4)$$$ do not have a common neighboring cell.