CF1758E Tick, Tock

Winden 镇的钟表匠 Tannhaus 制作了一些神秘的时钟，这些时钟以 $h$ 小时为周期，编号从 $0$ 到 $h-1$。有一天，他决定用这些时钟制作一个谜题。 这个谜题由一个 $n \times m$ 的时钟网格组成，每个时钟始终准确地显示某一个小时（即不会处于两个小时之间）。每次操作时，他可以选择任意一行或一列，将该行或该列的所有时钟的时间向前拨快一小时 $^\dagger$。 如果可以通过若干次操作使得所有时钟显示相同的时间，则称该时钟网格是可解的。 在制作谜题的过程中，Tannhaus 忽然担心这个网格可能无法被解出。网格中的部分格子已经有时钟显示了某个初始时间，其余格子为空。 给定部分完成的时钟网格，请你计算有多少种方法可以为空白格子分配时钟的初始时间，使得整个网格是可解的。答案可能非常大，请输出对 $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$ 个整数，描述时钟网格。第 $i$ 行第 $j$ 列的整数 $x$（$-1 \leq x < h$）表示该格子的初始时间，若 $x = -1$，则表示该格子为空。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示有多少种方法可以为空白格子分配时钟的初始时间，使得整个网格是可解的。答案对 $10^9+7$ 取模。

对于第一个样例，时钟的一种可能配置如下： | 1 | 0 | 3 | | :-----------: | :-----------: | :-----------: | | 0 | 3 | 2 | 这是可解的，因为可以： 1. 将中间一列向前拨快一小时。 2. 将第三列向前拨快一小时。 3. 再将第三列向前拨快一小时。 4. 将第二行向前拨快一小时。 之后，所有时钟都显示同一个小时。对于第二个测试用例，可以证明不存在任何可解的时钟配置。 由 ChatGPT 4.1 翻译