//Author:Dream_Flynn(luogu uid=578398)
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int k=0;
	bool f=false;
	char c=getchar();
	while(!isdigit(c)){
		f=(f||c=='-');
		c=getchar();
	}
	while(isdigit(c)){
		k=(k<<3)+(k<<1)+(c^48);
		c=getchar();
	}
	return f?-k:k;
}
inline void write(int d,char end_ch='\n'){
	if(d<0){
		d=-d;
		putchar('-');
	}
	int stk[32],top=0;
	do{
		top++;
		stk[top]=d%10;
		d/=10;
	}while(d);
	for(int i=top;i;i--){
		putchar(stk[i]^48);
	}
	putchar(end_ch);
}
const int mod=1e9+7;
int n,m,v,ans;
namespace PlanBF{
	map<int,int> mp;
	int a[200005],b[200005],C[100005],D[100005],val[200005];
	bool check(){
		for(int i=1;i<n;i++){
			if(val[i]==a[i]&&val[i+1]!=b[i]){
				return false;
			}
		}
		return true;
	}
	bool getval(int d){
		if(d==n+1){
			bool asd=check();
			//cerr<<"\tcheck:"<<asd<<endl;
			return asd;
		}
		if(mp[d]){
			val[d]=mp[d];
			bool asd=getval(d+1);
			//cerr<<"\tmp[d]:"<<asd<<endl;
			return asd;
		}
		else{
			for(int i=1;i<=v;i++){
				val[d]=i;
				bool ok=getval(d+1);
				//cerr<<"\tok:"<<ok<<endl;
				if(ok){
					return true;
				}
			}
			//cerr<<"\tfalse\n";
			return false;
		}
	}
	void getab(int d){
		if(d==n){
			if(getval(1)){
				ans++;
				ans%=mod;
			}
			return;
		}
		for(int i=1;i<=v;i++){
			a[d]=i;
			for(int j=1;j<=v;j++){
				b[d]=j;
				getab(d+1);
			}
		}
	}
	void main(){
		mp.clear();
		//cerr<<"!\n";
		for(int i=1;i<=m;i++){
			C[i]=read();
			D[i]=read();
			if(mp[C[i]]&&mp[C[i]]!=D[i]){
				write(0);
				return;
			}
			mp[C[i]]=D[i];
		}
		//cerr<<"!\n";
		ans=0;
		getab(1);
		//cerr<<"!\n";
		write(ans);
	}
}
/*namespace PlanA{
	#define int long long
	const int N=1e5+5,mod=1e9+7;
	int val[N],ans;
	void main(){
		for(int i=1;i<=m;i++){
			int x=read();
			val[x]=read();
		}
		for(int i=1;i<=n;i++){
			ans=(ans+((v-1)*v)%mod)%mod;
		}
		int tmp=0;
		for(int i=n;i>1;i--){
			if(b[i-1]==val[i]){
				tmp=(tmp<<1)%mod;
			}
		}
		write((ans+tmp)%mod);
	}
	#undef int
}*/
void Dream_Flynn_T2(){
	n=read();
	m=read();
	v=read();
	if(n<=12){	
		PlanBF::main();
		return;
	}
	else if(n==m){
		//PlanA::main();
		return;
	}
}
int main(){
	//freopen("1.in","r",stdin);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T=read();
	while(T--){
		Dream_Flynn_T2();
	}
	return 0;
}
