write a go solution for E. She knows...time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputD. Pippy is preparing for a "black-and-white" party at his home. He only needs to repaint the floor in his basement, which can be represented as a board of size nxm.After the last party, the entire board is painted green, except for some k cells (x_1,y_1),(x_2,y_2),ldots,(x_k,y_k), each of which is painted either white or black. For the upcoming party, D. Pippy wants to paint each of the remaining green cells either black or white. At the same time, he wants the number of pairs of adjacent cells with different colors on the board to be even after repainting.Formally, if A = \left\{((i_1, j_1), (i_2, j_2)) \ | \ 1 \le i_1, i_2 \le n, 1 \le j_1, j_2 \le m, i_1+j_1<i_2+j_2, |i_1-i_2|+|j_1-j_2| = 1, \operatorname{color}(i_1, j_1) \neq \operatorname{color}(i_2, j_2) \right\}, where operatornamecolor(x,y) denotes the color of the cell (x,y), then it is required that |A| be even.Help D. Pippy find the number of ways to repaint the floor so that the condition is satisfied. Since this number can be large, output the remainder of its division by 10^9+7.InputEach test consists of several test cases. The first line of the input data contains one integer t (1<=t<=10^4) — the number of test cases. The description of the test cases follows.The first line of each test case contains three integers n,m,k (3<=n,m<=10^9; 1<=k<=2*10^5) — the dimensions of the board and the number of cells that are initially not green.In the i-th of the following k lines of each test case, there are three integers x_i,y_i and c_i (1<=x_i<=n;1<=y_i<=m; c_iin0,1) — the coordinates of the cell and its color (if white, then c_i=0; if black, then c_i=1). It is guaranteed that all cells are distinct.It is guaranteed that the sum of k across all test cases does not exceed 2*10^5.OutputFor each test case, output a single integer — the answer modulo 10^9+7.ExampleInput23 3 61 1 01 2 11 3 03 1 13 2 03 3 13 4 121 1 01 2 11 3 01 4 12 1 12 2 02 3 12 4 03 1 03 2 13 3 03 4 1Output4
0
NoteIn the first test case, there are exactly 4 ways to paint the green cells (2,1),(2,2),(2,3), namely: (1,1,0),(0,0,1),(1,0,0),(0,1,1) (the colors are indicated in the same order as the cells), as shown below.  Example 1. In the second test case, all cells of the board are already painted, and the number of pairs of adjacent cells with different colors on the board is odd, so the answer is zero.. Output only the code with no comments, explanation, or additional text.