← 返回题目列表

Codeforces · 2092/E

E. 她知道……

中文机器翻译题面 查看原题

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$$$。

示例

输入
复制

2
3 3 6
1 1 0
1 2 1
1 3 0
3 1 1
3 2 0
3 3 1
3 4 12
1 1 0
1 2 1
1 3 0
1 4 1
2 1 1
2 2 0
2 3 1
2 4 0
3 1 0
3 2 1
3 3 0
3 4 1

输出
复制

4
0

注意

在第一个测试用例中,有 $$$4$$$ 种方法来绘制绿色单元格 $$$(2, 1), (2, 2), (2, 3)$$$,即: $$$(1, 1, 0), (0, 0, 1), (1, 0, 0), (0, 1, 1)$$$ (颜色的顺序与细胞),如下所示。

示例 1。

在第二个测试用例中,板上的所有单元格都已涂色,并且板上不同颜色的相邻单元格对的数量是奇数,因此答案为零。