[好题][图论][思维]Tick, Tock Codeforces1758E

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

The puzzle consists of an n×mn×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††.

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‡‡ to assign clocks in the empty cells so that the grid is solvable. The answer can be enormous, so compute it modulo 109+7109+7.

†† If a clock currently displays hour tt and is shifted one hour forward, then the clock will instead display hour (t+1)modh(t+1)modh.

‡‡ Two assignments are different if there exists some cell with a clock that displays a different time in both arrangements.

Input

The first line of input contains tt (1≤t≤5⋅1041≤t≤5⋅104) — the number of test cases.

The first line of each test case consists of 3 integers nn, mm, and hh (1≤n,m≤2⋅1051≤n,m≤2⋅105; 1≤h≤1091≤h≤109) — 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 nn lines each contain mm integers, describing the clock grid. The integer xx (−1≤x<h−1≤x<h) in the ii-th row and the jj-th column represents the initial hour of the corresponding clock, or if x=−1x=−1, an empty cell.

It is guaranteed that the sum of n⋅mn⋅m over all test cases does not exceed 2⋅1052⋅105.

Output

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 109+7109+7.

Example

input

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

output

4

0

73741817

0

1

题意： 给出一个h进制下n*m的矩阵，其中有些位置为-1，表示初始值可以任意指定，现在每次操作可以将一列或一行上的所有数+1，问有多少种初始值分配方案能够使矩阵经过若干次操作后数值相同。

分析： 这是一道很难想到的图论题，但是想到和图结合以后会简单一些。首先将n行和m列抽象成n+m个点，矩阵a[i][j]则抽象为i行和j列上的一条边，其中这n+m个点具有各自的点权，点权值就是对该行或列进行+1操作的次数。对于a[i][j]为-1的边暂时先不去建，只建当前存在的那些边，这样整幅图上就会存在若干个连通块。由于最终所有矩阵上的值要相同，所以每个连通块上的每个点都存在点权上的限制，比如有一边权为k的边(u, v)，必须保证(val[u]+val[v]+k)%h全部相同，因为(val[u]+val[v]+k)%h这个值就是最终矩阵上的数值。不妨设最终矩阵上的值全为0，那么任意具有边权k的边(u, v)就需要(val[u]+val[v]+k)%h == 0，在这个限制下只要确定连通块上的某一点的点权那整个连通块点权都确定了。接下来考虑还没加进来的-1边，可以知道这些-1边最终会让这些连通块完全连通，并且若有一条-1边连接(u, v)，且u和v分别属于两不同连通块，那么这条-1边的边权可以任取[0, h)中的每一个值，这是因为u和v的点权可以任取[0, +∞)中的任何值，所以边权总能凑出来这h种可能。因此设最终连通块个数为cnt，则答案为h^(cnt-1)。另外每个连通块不一定合法，还需要用bfs进行一下检查，如果存在某个不合法的连通块，那答案直接就是0。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#define int long long
#define pii pair<int, int>
using namespace std;

const int mod = 1e9+7; 
vector<pii> to[400005];
int val[400005];//记录点权 
int n, m, h;

int ksm(int base, int power){
	int ans = 1;
	while(power){
		if(power&1)
			ans = ans*base%mod;
		power >>= 1;
		base = base*base%mod;
	}
	return ans;
}

bool bfs(int now){
	queue<int> q;
	q.push(now);
	while(q.size()){
		int x = q.front();
		q.pop();
		for(int i = 0; i < to[x].size(); i++){
			int v = to[x][i].second, w = to[x][i].first;
			if(val[v] == -1){
				val[v] = ((-w-val[x])%h+h)%h;
				q.push(v);
			} 
			else{
				if((val[v]+w+val[x])%h != 0) 
					return false;
			}
		}
	}
	return true;
}

signed main(){
	int T;
	cin >> T;
	while(T--){
		scanf("%lld%lld%lld", &n, &m, &h);
		for(int i = 1; i <= n+m; i++){
			to[i].clear();
			val[i] = -1;
		}
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++){
				int t;
				scanf("%lld", &t);
				if(t != -1){
					to[i].push_back(make_pair(t, j+n));
					to[j+n].push_back(make_pair(t, i));
				}
			}
		int cnt = 0;//连通块个数 
		bool flag = true;
		for(int i = 1; i <= n+m; i++){
			if(val[i] == -1){
				cnt++;
				val[i] = 0;
				if(!bfs(i)){
					flag = false;
					break;
				}
			}
		} 
		if(flag) printf("%lld\n", ksm(h, cnt-1));
		else puts("0");
	} 

    return 0;
}