write a go solution for 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 nxm. 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<=i<=2k), these cells must share a common side. Additionally, the path must be simple, meaning that for no pair of indices ineqj 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<=t<=3*10^4). The description of the test cases follows. The first line of each test case contains three integers n, m, and k (1<=n,m<=1000, n*m>=3, 1<=k<=lfloorfrac12(nm-1)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<=x_2i-1<=n, 1<=y_2i-1<=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*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.. Output only the code with no comments, explanation, or additional text.