#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,mod=1e9+7;
int n,m,v;
map<int,int>mp;
int a[N],b[N];
struct te{
	int x,y;
}lc[N];
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans*=a;
		a*=a;
		ans%=mod;
		a%=mod;
		b>>=1;
	}
	return ans;
}
void solve(){
	sort(a+1,a+m+1);
	int cnt=n-1;
	for(int i=2;i<=m;i++){
		if(a[i]==a[i-1]+1)cnt--;
	}
	int ans=ksm(v*v%mod,cnt);
	ans=(ans*ksm((v*v-v+1)%mod,n-1-cnt))%mod;
//	cout<<n-1<<" "<<cnt<<"\n";
	cout<<ans<<"\n";
}
int an=0;
int st[N];
void dfs(int u){
	if(u>=n){
		for(int i=1;i<n;i++){
			if(st[i]==0||st[i+1]==0)continue;
			if(lc[i].x==st[i]&&lc[i].y!=st[i+1])return;
		}
		an++;
		return;
	}
	lc[u]=(te){1,1};
	dfs(u+1);
	lc[u]=(te){1,2};
	dfs(u+1);
	lc[u]=(te){2,1};
	dfs(u+1);
	lc[u]=(te){2,2};
	dfs(u+1);
}

void solve1(){
	memset(st,0,sizeof st);
	for(int i=1;i<=m;i++){
		st[a[i]]=b[i];
	}
	an=0;
	dfs(1);
	cout<<an<<"\n";
}
void solve2(){
	int ans=ksm((v*v-v+1)%mod,n-1);
	cout<<ans<<"\n";
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		mp.clear();
		int f=1,gx=1;
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			a[i]=u,b[i]=v;
			if(mp[u])gx=0;
			if(mp[u]&&mp[u]!=v){
				puts("0");
				f=0;
				break;
			}
			mp[u]=v;
		}
		if(!f)continue;
		if(gx&&m==n){
			solve2();
			continue;
		}
		if(n<=12&&v<=2)solve1();
		else solve();
	}
	
	return 0;
} 
/*
*/
