D. Pippy 正在家里准备一场“黑白”派对。他只需要重新粉刷地下室的地板,这可以表示为一块大小为 $$$n \times m$$$ 的木板。
最后一场比赛结束后,整个棋盘都被漆成绿色,除了一些 $$$k$$$ 单元格 $$$(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$$$,每个单元格被漆成白色或黑色。为了即将到来的派对,D. Pippy 想要画画 每个 剩余的绿色单元格为黑色或白色。同时,他希望重新涂漆后,板上不同颜色的相邻单元格对的数量是偶数。
形式上,如果 $$$$$$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 \lt 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\},$$$$$$ 其中 $$$\operatorname{color}(x, y)$$$ 表示单元格 $$$(x, y)$$$ 的颜色,则要求 $$$|A|$$$ 为偶数。
帮助 D. Pippy 找出重新粉刷地板以满足条件的方法的数量。由于该数字可能很大,因此输出除以 $$$10^9 + 7$$$ 的余数。
输入
每个测试由多个测试用例组成。输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n, m, k$$$ ($$$3 \le n, m \le 10^9$$$; $$$1 \le k \le 2 \cdot 10^5$$$) — 棋盘的尺寸和最初不是绿色的单元格数量。
在每个测试用例的以下 $$$k$$$ 行的第 $$$i$$$ 行中,有三个整数 $$$x_i、y_i$$$ 和 $$$c_i$$$ ($$$1 \le x_i \le n; 1 \le y_i \le m$$$; $$$c_i \in \{0, 1\}$$$) —单元格的坐标及其颜色(如果是白色,则 $$$c_i = 0$$$;如果是黑色,则 $$$c_i = 1$$$)。保证所有单元格都是不同的。
保证所有测试用例的 $$$k$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 答案模 $$$10^9 + 7$$$。
示例
输入复制
23 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 1
输出复制
4 0
注意
在第一个测试用例中,有 $$$4$$$ 种方法来绘制绿色单元格 $$$(2, 1), (2, 2), (2, 3)$$$,即: $$$(1, 1, 0), (0, 0, 1), (1, 0, 0), (0, 1, 1)$$$ (颜色的顺序与细胞),如下所示。
示例 1。 在第二个测试用例中,板上的所有单元格都已涂色,并且板上不同颜色的相邻单元格对的数量是奇数,因此答案为零。