E1. Billetes MX (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. В этой версии гарантируется, что $$$q = 0$$$. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Целочисленная сетка $$$A$$$ с $$$p$$$ строками и $$$q$$$ столбцами называется красивой, если:

  • Все элементы сетки являются целыми числами от $$$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$$$ ячеек. Поликарп хочет узнать, сколькими способами он может распределить целые числа по незаполненным ячейкам, чтобы сетка стала красивой.

Однако Монокарп считает, что эта задача слишком проста. Поэтому он выполнит $$$q$$$ обновлений сетки. В каждом обновлении он будет выбирать незаполненную ячейку и присваивать ей целое число. Заметим, что эти обновления перманентны. То есть изменения, внесенные в сетку, будут применяться при обработке будущих обновлений.

Для каждого из $$$q + 1$$$ состояния сетки (начального состояния и после каждого из $$$q$$$ запросов) определите количество способов, которыми Поликарп может присвоить целые числа незаполненным ячейкам, чтобы сетка стала красивой. Поскольку это число может быть очень большим, от вас требуется только вывести их значения по модулю $$$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$$$.

Пример
Входные данные
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
489373567
Примечание

В первом наборе входных данных мы имеем следующую сетку:

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

Можно доказать, что единственным допустимым значением для ячейки $$$(3, 3)$$$ является $$$0$$$.