CF1758E.Tick, Tock

Tannhaus, the clockmaker in the town of Winden, makes mysterious clocks that measure time in $h$ hours numbered from $0$ to $h-1$. One day, he decided to make a puzzle with these clocks.

The puzzle consists of an $n \times m$ grid of clocks, and each clock always displays some hour exactly (that is, it doesn't lie between two hours). In one move, he can choose any row or column and shift all clocks in that row or column one hour forward$^\dagger$.

The grid of clocks is called solvable if it is possible to make all the clocks display the same time.

While building his puzzle, Tannhaus suddenly got worried that it might not be possible to make the grid solvable. Some cells of the grid have clocks already displaying a certain initial time, while the rest of the cells are empty.

Given the partially completed grid of clocks, find the number of ways$^\ddagger$ to assign clocks in the empty cells so that the grid is solvable. The answer can be enormous, so compute it modulo $10^9 + 7$.

$^\dagger$ If a clock currently displays hour $t$ and is shifted one hour forward, then the clock will instead display hour $(t+1) \bmod h$.

$^\ddagger$ Two assignments are different if there exists some cell with a clock that displays a different time in both arrangements.

温登镇的钟表匠坦豪斯制作了一种神秘的钟表，其时间以 $h$ 小时为周期进行计量，小时数编号为 $0$ 至 $h-1$。某日，他决定用这些钟表设计一道谜题。

该谜题由一个 $n \times m$ 的钟表网格构成，每个钟表始终精确显示某一整点时刻（即不会处于两个整点之间）。在一次操作中，他可以选择任意一行或一列，并将该行或该列中的所有钟表向前拨动一小时$^\dagger$。

若存在一系列操作使得网格中所有钟表均显示同一时刻，则称该钟表网格是可解的。

在构造谜题的过程中，坦豪斯突然担心：该网格可能根本无法变得可解。网格中部分格子已预先放置了显示特定初始时刻的钟表，其余格子则为空。

给定一个部分填充的钟表网格，请计算有多少种方式$^\ddagger$ 为所有空格子分配钟表（即指定其显示的时刻），使得整个网格变为可解的。答案可能极大，请对 $10^9 + 7$ 取模输出。

$^\dagger$ 若某钟表当前显示时刻 $t$，将其向前拨动一小时后，该钟表将显示时刻 $(t+1) \bmod h$。

$^\ddagger$ 若存在某个格子，在两种分配方案中该格子上的钟表所显示的时刻不同，则称这两种分配方案不同。

The first line of input contains $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases.

The first line of each test case consists of 3 integers $n$, $m$, and $h$ ($1 \leq n, m \leq 2 \cdot 10^5$; $1 \leq h \leq 10^9$) — the number of rows in the grid, the number of columns in the grid, and the number of the hours in the day respectively.

The next $n$ lines each contain $m$ integers, describing the clock grid. The integer $x$ ($-1 \leq x \lt h$) in the $i$-th row and the $j$-th column represents the initial hour of the corresponding clock, or if $x = -1$, an empty cell.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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$ 个整数，用于描述时钟网格。第 $i$ 行第 $j$ 列的整数 $x$（$-1 \leq x \lt h$）表示对应时钟的初始时刻；若 $x = -1$，则表示该格子为空。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output the number of ways to assign clocks in the empty cells so that the grid is solvable. The answer can be huge, so output it modulo $10^9 + 7$.

对于每个测试用例，输出在空白格子中放置时钟的方式数目，使得整个网格可解。答案可能非常大，因此请对 $10^9 + 7$ 取模后输出。

For the first sample, this is a possible configuration for the clocks:

1

0

3

0

3

2

This is solvable since we can:

1. Move the middle column forward one hour.
2. Move the third column forward one hour.
3. Move the third column forward one hour.
4. Move the second row forward one hour.

After that all the clocks show one hour.

For the second test case, it can be shown that there are no possible solvable clock configurations.

对于第一个样例，以下是一种可能的钟表配置：

1

0

3

0

3

2

该配置是可解的，因为我们能够：

1. 将中间一列向前拨动一小时。
2. 将第三列向前拨动一小时。
3. 将第三列再次向前拨动一小时。
4. 将第二行向前拨动一小时。

此后，所有钟表均显示一小时。

对于第二个测试用例，可以证明不存在任何可解的钟表配置。