← 返回题目列表

Codeforces · 1758/E

E. 勾选,勾选

中文机器翻译题面 查看原题

温登镇的钟表匠坦豪斯 (Tannhaus) 制造神秘的时钟,以 $$$h$$$ 小时为单位测量时间,编号从 $$$0$$$ 到 $$$h-1$$$。有一天,他决定用这些时钟制作一个拼图。

这个谜题由一个 $$$n \times m$$$ 时钟网格组成,每个时钟总是准确地显示某个小时(也就是说,它不介于两个小时之间)。一次移动,他可以选择任意行或列,并将该行或列中的所有时钟向前移动一小时$$$^\dagger$$$。

如果可以使所有时钟显示相同的时间,则时钟网格称为可解的。

在构建谜题时,Tannhaus 突然担心网格可能无法解决。网格的某些单元格的时钟已经显示某个初始时间,而其余单元格为空。

给定部分完成的时钟网格,找到在空单元格中分配时钟的方法$$$^\ddagger$$$ 的数量,以便网格可解。答案可能很大,因此请以 $$$10^9 + 7$$$ 为模进行计算。

$$$^\dagger$$$ 如果时钟当前显示小时 $$$t$$$ 并向前移动一小时,则时钟将显示小时 $$$(t+1) \bmod h$$$。

$$$^\ddagger$$$ 如果存在某些单元格的时钟在两种排列中显示不同的时间,则两个分配是不同的。

输入

输入的第一行包含 $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — 测试用例的数量。

每个测试用例的第一行由 3 个整数组成 $$$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

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

输出 #1

4
0
73741817
0
1

注意

对于第一个示例,这是时钟的可能配置:103032

这是可以解决的,因为我们可以:

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

对于第二个测试用例,可以证明不存在可能的可解时钟配置。