#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int T,n,m,v;
struct node{
	int c,d;
} a[100010];
//bool bb[100010];
int ksm(int a,int b){
	int res=1ll;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int ta[20],tb[20],sum,aa[20],bb[20];
bool check(int dep){
	if(dep>n){
		return true;
	}
	bool flag=false;
	if(bb[dep]){
		if(dep>1&&aa[dep-1]==ta[dep-1]&&bb[dep]!=tb[dep-1]) return false;
		aa[dep]=bb[dep];
		flag=check(dep+1);
	}
	else for(int i=1;i<=v;i++){
		if(dep>1&&aa[dep-1]==ta[dep-1]&&i!=tb[dep-1]) continue;
		aa[dep]=i;
		flag|=check(dep+1);
		if(flag) break;
	}
	return flag;
}
void dfs(int dep){
	if(dep>=n){
		sum+=check(1);
		return ;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			ta[dep]=i,tb[dep]=j;
			dfs(dep+1);
		}
	}
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		memset(bb,0,sizeof(bb));
		bool A=(n==m),ff=true;
		for(int i=1;i<=m;i++){
			cin>>a[i].c>>a[i].d;
			if(a[i].c!=i) A=false;
//			if(a[i].d!=1) B=false;
			if(a[i].c<=20){
				if(bb[a[i].c]&&bb[a[i].c]!=a[i].d) ff=false;
				bb[a[i].c]=a[i].d;
//				cout<<a[i].c<<' '<<bb[a[i].c]<<'\n';
			}
		}
		if(!ff){
			cout<<0<<'\n';
			continue;
		}
		if(A){
			int ans=1ll;
			for(int i=1;i<n;i++) ans=1ll*ans*(1ll*(v-1)*v%mod+1)%mod;
			ans=(ans+mod)%mod;
			cout<<ans<<'\n';
		}
		else if(n<=12){
			sum=0;
			dfs(1);
			cout<<sum<<'\n';
		}
		else {
			int ans=1ll;
			ans=ans*ksm(v,(n-1)*2)%mod;
			ans=(ans+mod)%mod;
			cout<<ans<<'\n';
		}
//		else cout<<0<<'\n';
//		else if(B){
//			int lst=0,ans=1ll;
//			for(int i=1;i<min(n,100000ll);i++){
//				if(!bb[i]) continue;
//				ans=ans*(ksm(v,(i-lst)*2)-ksm(v,i-lst-1))%mod;
//				lst=i;
//			}
//			if(lst!=n) ans=ans*ksm(v,(n-lst-1)*2)%mod;
//			ans=(ans+mod)%mod;
//			cout<<ans<<'\n';
//		}
	}
	return 0;
}
/*
1
2 1 3
1 1

1
2 1 3
2 1

3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

*/
