← 返回题目列表

Codeforces · 2022/E1

E1. Billetes MX(简易版)

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

这是问题的简单版本。在此版本中,保证 $$$q = 0$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

具有 $$$p$$$ 行和 $$$q$$$ 列的整数网格 $$$A$$$ 被称为漂亮,如果:

- 网格的所有元素都是 $$$0$$$ 和 $$$2^{30}-1$$$ 之间的整数,并且
- 对于任何子网格,角点处的值的 XOR 等于 $$$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$$$ 单元格。波利卡普想知道他可以用多少种方式将整数分配给未填充的单元格,以使网格变得漂亮。

然而,Monocarp 认为这个问题太简单了。因此,他将在网格上执行 $$$q$$$ 更新。在每次更新中,他都会选择一个未填充的单元格并为其分配一个整数。请注意,这些更新是持久的。也就是说,对网格所做的更改将在处理未来更新时应用。

对于网格的每个 $$$q + 1$$$ 状态、初始状态以及每个 $$$q$$$ 查询之后,确定 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$$$ 行应包含网格模 $$$10^9 + 7$$$ 的第 $$$i$$$ 状态的答案。

示例

输入 #1

2
3 3 8 0
2 1 6
3 2 12
1 2 6
2 2 0
1 3 10
1 1 0
2 3 12
3 1 10
2 5 2 0
1 1 10
1 2 30

输出 #1

1
489373567

注意

在示例的第一个测试用例中,我们有以下网格:

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

可以证明,tile $$$(3, 3)$$$ 的唯一有效值为$$$0$$$。