Олимпиадный тренинг

Задача . E. Тик-так


Танхаус, часовщик в городе Винден, делает необычные часы, измеряющие время в \(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\).

Примечание

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

103
032

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

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

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


Примеры
№Входные данныеВыходные данные
1
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
Статистика успешных решений по компиляторам
 Кол-во
С++5