#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
const int mod=1e9+7;
#define int long long 
int C[N],D[N],ans,n,tot,m,v,dp[N];
map<int,int> Vus;
struct node{
	int c,d;
}a[N];
bool cmp(node A,node B){
	return A.c<B.c;
}
int Quickpow(int A,int B){
	int Ans=1,now=A;
	while(B>0){
		if(B&1)	Ans*=now,Ans%=mod;
		now*=now,now%=mod;
		B>>=1;
	} 
	return Ans;
} 
bool check(){
	int now=-1;
	for(int i=1;i<n;i++){
		if(Vus[i])	now=Vus[i];
		if(now==a[i].c)	now=a[i].d;
		else now=-1;
		if(Vus[i+1]!=0&&now!=Vus[i+1]&&now!=-1)	return false;
	} 
	return true;
}
void dfs(int dis){
	if(dis==n){
		if(check())	ans++;
		return ;
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
			a[dis].c=i,a[dis].d=j,dfs(dis+1);
} 
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		ans=0;
		cin>>n>>m>>v; int step=(v%mod*v%mod)%mod;
		bool f=true;
		for(int i=1;i<=m;i++){
			cin>>C[i]>>D[i];
			if(Vus[C[i]]==0)	Vus[C[i]]=D[i];
			else{
				if(Vus[C[i]]!=D[i]) f=false;
			}
		}
		if(!f){
			cout<<0<<endl; 
			for(int i=1;i<=m;i++)	Vus[C[i]]=0;
			continue;
		}
		if(m==1){
			cout<<Quickpow(step,n-1)<<endl;
			for(int i=1;i<=m;i++)	Vus[C[i]]=0;
			continue;
		} 
		dfs(1);
		cout<<ans<<endl;
		for(int i=1;i<=m;i++)	Vus[C[i]]=0;
	}
	return 0;
}
/*
1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2



*/ 
