E. Тик-так
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Танхаус, часовщик в городе Винден, делает необычные часы, измеряющие время в $$$h$$$ часах, пронумерованных от $$$0$$$ до $$$h-1$$$. Однажды он решил сделать из таких часов загадку.

Загадка состоит из таблицы размера $$$n \times m$$$ с часами, где каждые часы показывают какой-то час ровно (то есть время не лежит между двумя ровными часами). За один ход он может выбрать строку или столбец и перевести все часы в строке или столбце на час вперед$$$^\dagger$$$.

Таблица с часами называется решаемой, если можно сделать так, чтобы все часы показывали одно и то же время.

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

Вам дана частично заполненная таблица с часами, найдите количество способов$$$^\ddagger$$$ заполнить пустые клетки часами так, чтобы таблица была решаемой. Так как ответ может быть большим, выведите его по модулю $$$10^9 + 7$$$.

$$$^\dagger$$$ Если часы показывают $$$t$$$ часов, и их переводят на час вперед, они будут показывать $$$(t+1) \bmod h$$$ часов.

$$$^\ddagger$$$ Два способа считаются различными, если существует клетка с часами, в двух способах показывающими различное время.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$h$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$; $$$1 \leq h \leq 10^9$$$) — количество строк и столбцов в таблице, а также количество часов на каждых часах.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел, описывающих часы в таблице. Число $$$x$$$ ($$$-1 \leq x < h$$$) в $$$i$$$-м ряду в $$$j$$$-м столбце показывает изначальное время на соответствующих часах, а если $$$x = -1$$$, то эта клетка пуста.

Гарантируется, что сумма значений $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите число способов заполнить пустые клетки таблицы так, чтобы загадка была решаемой. Так как ответ может быть большим, выведите его по модулю $$$10^9 + 7$$$.

Пример
Входные данные
5
2 3 4
1 0 -1
-1 -1 2
2 2 10
1 2
3 5
4 5 1024
1 -1 -1 -1 -1
-1 -1 -1 1000 -1
-1 -1 -1 -1 69
420 -1 -1 999 -1
3 3 3
-1 -1 1
2 -1 1
2 -1 2
3 3 3
1 -1 2
-1 0 -1
-1 1 0
Выходные данные
4
0
73741817
0
1
Примечание

В первом примере например подходит следующая конфигурация часов:

103
032

Она решаемая, например, так:

  1. Перевести часы в среднем столбце на час.
  2. Перевести часы в третьем столбце на час.
  3. Перевести часы в третьем столбце на час.
  4. Перевести часы во второй строке на час.
После этого все часы показывают один час.

Во втором примере можно показать, что нет решаемых конфигураций.