#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5,mod=1e9+7;
int n,m,v,a[maxn],ans,p[maxn],q[maxn],b[maxn],c[maxn];
map<long long,bool>vi;
bool check(){
	for(int i=1;i<n;i++){
		for(int j=1;j<n;j++){
//			cout<<" "<<i<<" "<<j<<" ";
//			for(int l=1;l<=n;l++)cout<<a[i]<<" ";
//			cout<<"\n";
			for(int l=1;l<n;l++){
				if(a[l]==p[i]&&a[l+1]!=q[j]){
					return 0;
				}
			}
		}
	}
	long long tmp=0;
	for(int i=1;i<n;i++)tmp=tmp*(long long)(v+1)+(long long)p[i];
	for(int i=1;i<n;i++)tmp=tmp*(long long)(v+1)+(long long)q[i];
	if(!vi[tmp]){
		vi[tmp]=1;
		return 1;
	}
	else return 0;
	
}
void dfs2(int x){
	if(x==n){
		if(check())ans++,ans%=mod;
		return ;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			p[x]=i,q[x]=j;
			dfs2(x+1);
		}
	}
}
void dfs(int x){
	if(x==n+1){
		dfs2(1);
		return ;
	}
	if(a[x]){
		dfs(x+1);
		return ;
	}
	for(int i=1;i<=v;i++)a[x]=i,dfs(x+1);
}
int qpow(int x,int y){
	int ans=1;
	while(y){
		if(y&1)ans=ans*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return ans;
}
void solve(){
	ans=0;
	vi.clear();
	cin>>n>>m>>v;
	if(m==1){
		cin>>m>>m;
		cout<<qpow(qpow(v,n-1),2)%mod<<"\n";
		return ;
	}
	else if(n<=12&&m<=12){
		for(int i=1;i<=n;i++)a[i]=0;
		while(m--){
			int x,y;
			cin>>x>>y;
			if(a[x]&&a[x]!=y){
				cout<<"0\n";
				return ;
			}
			else a[x]=y;
		}
		dfs(1);
		cout<<ans<<"\n";
	}
	else{
		for(int i=1;i<=max(n,v);i++)c[i]=b[i]=a[i]=0;//0->renyi,1->weiyi,-1->wujie
		while(m--){
			int x,y;
			cin>>x>>y;
			if(a[x]&&a[x]!=y){
				cout<<"0\n";
				return ;
			}
			else a[x]=y;
		}
		for(int i=1;i<n;i++){
			if(b[a[i]]==0){
				c[a[i]]=a[i+1];
				b[a[i]]=1;
			}
			else if(b[a[i]]==1){
				if(c[a[i]]==a[i+1]);
				else b[a[i]]=-1;
			}
		}
		int cnt=0;
		for(int i=1;i<=v;i++){
//			cout<<i<<" "<<b[i]<<"\n";
			if(b[i]==0)cnt+=v;
			else if(b[i]==1)cnt++;
//			else if(b[a[i]]==2)cnt++;
//			else if(b[a[i]]==-1)cnt++;
			cnt%=mod;
		}
		cout<<qpow(cnt,n-1)<<"\n";
	}
}
main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}
/*
3
5 1 2
1 2
6 5 2
4 2
5 1
4 2
2 2
2 1
7 1 2
4 1
*/
