#include<iostream>
#include<cstdio>
using namespace std;
long long t;
long long n,m,v;
long long ans=0;
long long a[1000005],b[1000005];
long long c[1000005],d[1000005];
const long long mod=1e9+7;
void dfs(long long x){//to make
	if(x==n){
		for(int i=1;i<=n;i++){
			if(d[i]&&c[i]&&d[i]!=c[i]){
				d[i]=c[i];
				return ;
			}
			if(d[i]&&d[i]==a[i]){
				d[i+1]=b[i];
			}
			d[i]=c[i];
		}
//		for(int i=1;i<n;i++)cout<<a[i]<<" "<<b[i]<<"\n";
//		cout<<'\n';
		ans++;
		ans%=mod;
		return ;
	}
	for(int i=1;i<=v;i++){
		a[x]=i;
		for(int j=1;j<=v;j++){
			b[x]=j;
			dfs(x+1);
		}
	}
	return ;
}
long long pow(long long x,long long y){
	long long ans=1;
	while(y){
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}
bool flg;
long long fac[1000005],inv[1000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	inv[n]=pow(fac[n],mod-2);
	for(int i=n-1;i>=1;i--)inv[i]=(i+1)*inv[i+1]%mod;
	return;
}
long long C(long long x,long long y){
	return fac[x]*inv[x-y]%mod*inv[y]%mod;
}
signed main(){
//	freopen("assign2.in","r",stdin);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--){
		flg=1;
		cin>>n>>m>>v;
		ans=0;
		if(m==1){
			for(int i=1;i<=m;i++){
				long long x,y;
				cin>>x>>y;
			}
			cout<<pow(v,2ll*(n-1ll))<<"\n";
		}else{
			if(m!=n)flg=0;
			for(int i=1;i<=n;i++)c[i]=d[i]=0;
			for(int i=1;i<=m;i++){
				long long x,y;
				cin>>x>>y;
				if(x!=i)flg=0;
				if(c[x]&&c[x]!=y){
					cout<<"0\n";
					goto ed;
				}
				c[x]=d[x]=y;
			}
			if(flg){
				init();
				int opt=1;
				for(int i=1;i<=n;i++)ans=(ans+opt*C(n-1,i)%mod%mod*pow(v,2ll*(i-1))%mod)%mod,opt=(opt==1?-1:1);
				cout<<ans<<"\n";
			}else{
				dfs(1);
				cout<<ans<<"\n";
			}
		}
		ed:;
	}
	return 0;
}
