#include<bits/stdc++.h>
using namespace std;
int T;
int n,m,v;
const long long P=1e9+7;
long long ans;
int tag[1000010];
int a[1000010],b[1000010];
int pos[1000010];
int dfs1(int x){
	if(x==n+1){
		for(int i=1;i<=n;++i){
			if(tag[i]!=0){
				if(tag[i]!=pos[i])return 0; 
			}
			if(i!=n){
				if(pos[i]==a[i]&&pos[i+1]!=b[i])return 0;
			}
		}
		return 1;
	}
	if(tag[x]==0){
		if(x!=1&&pos[x-1]==a[x-1]){
			pos[x]=b[x-1];
//			if(x!=n&&pos[x]==a[x]&&tag[x+1]!=0&&tag[x+1]!=b[x])return 0;
			return dfs1(x+1);
		}
		for(int i=1;i<=v;++i){
			pos[x]=v;
//			if(x!=n&&pos[x]==a[x]&&tag[x+1]!=0&&tag[x+1]!=b[x])continue;
			if(dfs1(x+1)==1)return 1;
		}return 0;
	}
	else{
		pos[x]=tag[x];
//		if(x!=n&&pos[x]==a[x]&&tag[x+1]!=0&&tag[x+1]!=b[x])return 0;
		return dfs1(x+1);
	}
}
void dfs0(int x){
	if(x==n){
		if(dfs1(1)==1)ans=(ans+1)%P; 
		return;
	}
	for(int i=1;i<=v;++i)
		for(int j=1;j<=v;++j){
			a[x]=i;b[x]=j;
			dfs0(x+1);
			a[x]=0;b[x]=0;
		}
}
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);
		for(int i=0;i<=n+5;++i)tag[i]=0;
		int g=0;
		for(int i=1;i<=m;++i){
			int p,x;
			scanf("%d%d",&p,&x);
			if(tag[p]!=0&&tag[p]!=x)g=1;
			tag[p]=x;
		}
		if(g==1){
			printf("0\n");
			continue;
		}
		dfs0(1);printf("%lld\n",ans);
	}return 0;
}
