CF2022E1.Billetes MX (Easy Version)

这是该问题的简单版本。在本版本中，保证 $q = 0$。只有当你同时解决了两个版本的问题时，才能进行 hack。

一个有 $p$ 行 $q$ 列的整数网格 $A$ 被称为美丽的，当且仅当：

• 网格中的所有元素都是 $0$ 到 $2^{30}-1$ 之间的整数；
• 对于任意子矩阵，其四个角的值的异或和等于 $0$。形式化地说，对于任意四个整数 $i_1$、$i_2$、$j_1$、$j_2$（$1 \le i_1 < i_2 \le p$；$1 \le j_1 < j_2 \le q$），都有 $A_{i_1, j_1} \oplus A_{i_1, j_2} \oplus A_{i_2, j_1} \oplus A_{i_2, j_2} = 0$，其中 $\oplus$ 表示按位异或运算。

现在有一个部分填充的整数网格 $G$，有 $n$ 行 $m$ 列，其中只有 $k$ 个格子被填充。Polycarp 想知道，有多少种方法可以给未填充的格子赋值，使得整个网格是美丽的。

然而，Monocarp 认为这个问题太简单了。因此，他会对网格进行 $q$ 次更新。在每次更新中，他会选择一个未填充的格子并赋予它一个整数。注意，这些更新是持久的，也就是说，对网格的更改会影响后续的所有更新。

对于每个 $q+1$ 个网格状态（初始状态及每次查询后的状态），请你计算 Polycarp 可以如何给未填充格子赋值，使得网格美丽的方案数。由于答案可能非常大，你只需要输出其对 $10^9+7$ 取模的结果即可。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含四个整数 $n$、$m$、$k$ 和 $q$（$2 \le n, m \le 10^5$；$0 \le k \le 10^5$；$q = 0$），分别表示行数、列数、已填充的格子数和更新次数。

接下来的 $k$ 行，每行包含三个整数 $r$、$c$ 和 $v$（$1 \le r \le n, 1 \le c \le m$；$0 \le v < 2^{30}$），表示 $G_{r, c}$ 被赋值为 $v$。

接下来的 $q$ 行，每行包含三个整数 $r$、$c$ 和 $v$（$1 \le r \le n, 1 \le c \le m$；$0 \le v < 2^{30}$），表示 $G_{r, c}$ 被赋值为 $v$。

保证所有赋值的 $(r, c)$ 坐标都是不同的。

保证所有测试用例中 $n$、$m$、$k$ 和 $q$ 的总和分别不超过 $10^5$。

对于每个测试用例，输出 $q+1$ 行。第 $i$ 行输出网格第 $i$ 个状态下的答案，对 $10^9+7$ 取模。

在示例的第一个测试用例中，网格如下：

$0$ $6$ $10$ $6$ $0$ $12$ $10$ $12$ $?$

可以证明，格子 $(3, 3)$ 唯一合法的取值为 $0$。

由 ChatGPT 4.1 翻译