#include<stdio.h>
using namespace std;
typedef long long ll;
const ll Maxn=1e5,mod=1e9+7,Maxa=5e3;
ll T,n,m,v,c[Maxn+10],d[Maxn+10],ans;
ll vis[Maxn+10];
bool check_1(){
	if(n<=9)
		return true;
	else
		return false;
}
ll a6[Maxa][100],cnta,ax[Maxa];
void dfs(ll x){
	if(x==n){
		cnta++;
		for(ll i=1;i<=n-1;i++)
			a6[cnta][i]=ax[i];
		return;
	}
	for(ll i=1;i<=v;i++){
		ax[x]=i;
		dfs(x+1);
	}
}
ll ai[Maxa+10],bi[Maxa+10],xi[Maxa+10];
bool check(){
	for(ll i=1;i<=n;i++)
		if(vis[i]){
			if(xi[i]!=d[i])
				return false;
		}
	for(ll i=1;i<n;i++){
		if(xi[i]!=ai[i])
			continue;
		if(xi[i+1]!=bi[i])
			return false;
	}
	return true;
}
void slove_1(){
	dfs(1);
//	printf("   %lld\n",cnta);
	for(ll i=1;i<=cnta;i++)
		for(ll i1=1;i1<=cnta;i1++){
			bool flap=false;
			for(ll i3=1;i3<=n-1;i3++)
				ai[i3]=a6[i][i3],bi[i3]=a6[i1][i3];
			for(ll i2=1;i2<=cnta;i2++){
				for(ll i3=1;i3<=n-1;i3++)
					xi[i3]=a6[i2][i3];
				xi[n]=1;
				if(check()){
					flap=true;
					break;
				}
				xi[n]=2;
				if(check()){
					flap=true;
					break;
				}
			}
			if(flap)
				ans++;
		}
	printf("%lld\n",(ans%mod)); 
	for(ll i=1;i<=cnta;i++)
		for(ll i1=1;i1<=Maxa;i1++)
			a6[i][i1]=0;
	cnta=0;
	return ;
}
bool check_A(){
	if(n!=m)
		return false;
	for(ll i=1;i<=n;i++)
		if(!vis[i])
			return false;
	return true;
}
void slove_A(){
	ans=1;
	for(ll i=1;i<=n-1;i++){
		ans=ans*(1ll+(v-1ll)*v%mod)%mod;
	}
	printf("%lld\n",(ans%mod));
	return ;
}
void xm(){
	for(ll i=1;i<=m+1;i++)
		c[i]=d[i];
	for(ll i=1;i<=n+1;i++)
		vis[i]=0;
	ans=cnta=n=m=v=0;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&T);
	for(ll i0=1;i0<=T;i0++){
		scanf("%lld%lld%lld",&n,&m,&v);
		bool flap=false;
		for(ll i=1;i<=m;i++){
			scanf("%lld%lld",&c[i],&d[i]);
			if(vis[c[i]]!=0)
				if(vis[c[i]]!=d[i])
					flap=true;
			vis[c[i]]=d[i];
		}
		if(flap){
			printf("0\n");
			xm();
			continue;
		}
		if(check_1()){
			slove_1();
			xm();
			continue;
		}
		if(check_A()){
			slove_A();
			xm();
			continue;
		}
		xm();
	}
	
} 
/*
5
5 1 2
1 2
6 5 2
4 2
5 1
4 2
2 2
2 1
7 1 2
4 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
12 2 2
7 2
7 2
*/
