#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int t,n,m,v,ans;
int a[N],b[N];
int c[N],d[N];
int bz[N];
int pw(int a,int b){
	int h=1;
	while(b){
		if(b&1){
			h=1ll*h*a%mod;
		}
		a=1ll*a*a%mod;
		b>>=1;
	}
	return h;
}
int ck(){
	for(int i=1;i<=n;i++){
		bz[i]=0;
	}
	for(int i=1;i<=m;i++){
		bz[c[i]]=d[i];
	}
	for(int i=1;i<n;i++){
		if(bz[i]==a[i]){
			if(bz[i+1]&&bz[i+1]!=b[i]){
				return 0;
			}
			bz[i+1]=b[i];
		}
	}
	return 1;
}
void dfsb(int x){
	if(x>=n){
		if(ck()){
			ans++;
		}
		return;
	}
	for(int i=1;i<=v;i++){
		b[x]=i;
		dfsb(x+1);
	}
}
void dfsa(int x){
	if(x>=n){
		dfsb(1);
		return;
	}
	for(int i=1;i<=v;i++){
		a[x]=i;
		dfsa(x+1);
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&v);
		int bj=0;
		if(m<n){
			bj=1;
		}
		for(int i=1;i<=m;i++){
			scanf("%d%d",&c[i],&d[i]);
			if(c[i]!=i){
				bj=1;
			}
		}
		if(bj==0){
			printf("%d\n",pw((1ll*v*(v-1)%mod+1)%mod,n-1));
			continue;
		}
//		if(m==1){
//			ans=0;
//			for(int i=0;i<=n-c[1];i++){
//				ans=(ans+1ll*pw(v,c[1]-1)*pw(v,c[1]-1)%mod)%mod;
//			}
//			printf("%d\n",ans);
//			continue;
//		}
//		if(v<=2){
			for(int i=1;i<=n;i++){
				bz[i]=0;
			}
			bj=0;
			for(int i=1;i<=m;i++){
				if(bz[c[i]]&&bz[c[i]]!=d[i]){
					bj=1;
					break;
				}
				bz[c[i]]=d[i];
			}
			if(bj==1){
				printf("0\n");
				continue;
			}
			ans=0;
			dfsa(1);
			printf("%d\n",ans);
//		}
	}
}
