温登镇的钟表匠坦豪斯 (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. 将第二行向前移动一小时。
对于第二个测试用例,可以证明不存在可能的可解时钟配置。