E. She knows...
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Д. Пиппи готовится к «черно-белой» вечеринке у себя дома. Ему осталось лишь перекрасить пол в своем подвале, который можно представить как доску размером $$$n \times m$$$.

После прошлой вечеринки вся доска покрашена в зеленый цвет, за исключением каких-то $$$k$$$ клеток $$$(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$$$, каждая из которых покрашена либо в белый, либо в черный цвет. Для предстоящей вечеринки Д. Пиппи хочет покрасить каждую из оставшихся зеленых клеток либо в черный, либо в белый цвет. При этом он хочет, чтобы после перекраски количество пар соседних разноцветных клеток на доске было четным.

Формально говоря, если $$$$$$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|$$$ было четным.

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

В $$$i$$$-й из следующих $$$k$$$ строк каждого набора входных данных содержатся три целых числа $$$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.

Во втором наборе все клетки доски уже покрашены, и при этом количество пар соседних разноцветных клеток на доске нечетно, поэтому ответ равен нулю.