#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define int long long
const int mod = 1e9+7;
int n,m,i,j,ans,t,v,c,d,a[N],x[N],y[N],f[1005][1005];
int dfs(int k,int nw){//当前的数是nw 
	if(k==n) return 1;
	int p=0;
	if(f[k][nw]!=-1) return f[k][nw];
	for(int i=1;i<=v;i++){//枚举xi=i 
		if(i==nw){//如果满足xi=a[i] 
			if(a[k+1]) p+=dfs(k+1,a[k+1]);
			else for(int j=1;j<=v;j++) p+=dfs(k+1,j),p%=mod;
		}
		else{
			for(int j=1;j<=v;j++){//枚举xi+1=j 
				if(a[k+1]) p+=dfs(k+1,a[k+1]);
				else p+=dfs(k+1,0);
				p%=mod;
			}
		}
		p%=mod;
	}
	return f[k][nw]=p;
}
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		b>>=1,a=a*a%mod;
	}
	return res;
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld",&n,&m,&v);
		int pp=0;
		if(m==1){
			printf("%lld\n",qpow(v*v%mod,n-1));
			pp=1;
		}
		if(!pp) for(i=1;i<=n;i++) a[i]=0;
		int flag=0,flag2=0;
		for(i=1;i<=m;i++){
			scanf("%lld%lld",&c,&d);
			if(!pp){
				if(c!=i) flag2=1;
				if(!a[c]) a[c]=d;
				else if(a[c] && a[c]!=d) flag=1;
			}
		}
		if(pp) continue;
		if(flag){
			puts("0");
			continue;
		}
		if(m==n && !flag2){
			ans=1;
			int res=0;
			for(int i=1;i<n;i++){
				res=(1+(v-1)*v)%mod;
				res%=mod,ans*=res,ans%=mod;
			}
			printf("%lld\n",ans);
			continue;
		}
		
		if(n<=1000 && m<=1000){
			for(i=1;i<=n;i++){
				for(j=0;j<=v;j++) f[i][j]=-1;
			}
			ans=0;
			ans=dfs(1,a[1]);
			printf("%lld\n",ans);
		}
		
	}
	return 0;
}
