#include<iostream>
#include<cstdio> 
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm> 
using namespace std;
const int N=1e6+86;
const int F=1911;
const int MOD=1e9+7;
int n,t,m,v;
int a[N],ai[F],bi[F];
int x[N],y[N],an[N];
int cnt;
long long ans=0;
void fcm(){
	bool l=true;
	memset(a,0,sizeof(a));
	memset(an,0,sizeof(an));
	for(int i=1;i<=m;i++){
		if(!a[x[i]]){
			a[x[i]]=y[i];
		}else if(a[x[i]]==y[i]) continue;
		else if(a[x[i]]!=y[i]) l=false;
	}
	if(l)
	for(int i=1;i<n;i++){
		if(a[i]==ai[i]){
			if(a[i+1]!=bi[i]&&a[i+1]!=0){
				l=false;
				break;
			}
		}
	}
	if(l) ans++,ans%=MOD;
	return;
}
void dfsb(int k){
	if(k==n){
		cnt++;
//		cout<<endl;
//		for(int i=1;i<n;i++){
//			cout<<bi[i]<<" ";
//		}
		fcm();
		return;
	} 
	for(int i=1;i<=v;i++){
		bi[k]=i;
		dfsb(k+1);
	}
} 
void dfsa(int k){
	if(k==n){
		dfsb(1);
		return;
	}
	for(int i=1;i<=v;i++){
		ai[k]=i;
		dfsa(k+1);
	}
}
void fn(){
	memset(a,0,sizeof(a));
	for(int i=1;i<=m;i++){
//		int x,y;
		scanf("%d%d",&x[i],&y[i]);
		a[x[i]]=y[i];
	}
	dfsa(1);
	printf("%lld\n",ans);
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		ans=0;
		scanf("%d%d%d",&n,&m,&v);
		if(n<=12)fn();
//		cout<<cnt; 
	}
	return 0;
}
