#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long v,t;
long long i,j,k,n,m,ans,a[1000005],c,d,ua[100005],ub[100005];
void dfs(long long x){
	if(x==n-1){
		for(long long i=1;i<n;i++){
			if(a[i]==ua[i]){
				if(a[i+1]!=-1 && a[i+1]!=ub[i]) return ;
			} 
		}
		ans++;
		return ;
	}
	for(long long i=1;i<=v;i++){
		for(long long j=1;j<=v;j++){
			ua[x+1]=i,ub[x+1]=j,dfs(x+1);
		}
	}
}
int fp(int x,int y){
	long long b=x,ret=1;
	while(y){
		if(y&1) ret=(ret*b)%mod;
		b=(b*b)%mod;
		y>>=1;
	}
	return ret;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin>>t;
	while(t--){
		ans=0;
		memset(ua,0,sizeof(ua));
		memset(ua,0,sizeof(ub));
		memset(a,-1,sizeof(a));
		cin>>n>>m>>v;
		for(i=1;i<=m;i++){
			cin>>c>>d;
			if(a[c]==-1) a[c]=d;
			else if(a[c]!=d) n=-1;
		}
		if(n==-1){
			cout<<0<<'\n';
			continue;
		} 
		if(n<=12){
			dfs(0);
			cout<<ans<<'\n';
		}
		else{
			ans=1;
			ans=fp(v,n);
			cout<<(ans)%mod<<'\n';
		}
	}
	return 0;
} 

/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

*/
