#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int mod=1e9+7;
map<long long,int>map1;
int mark,n,m,v,T,xx,yy,c[100005],d[100005],vis[100005];
int value[100005],a[1005],b[1005];
long long ans;
void dfs1(int x){
	if(x==n){
		long long cnt1=0,num=1;
		for(int i=1;i<=n-1;i++) cnt1+=num*a[i],num*=10;
		for(int i=1;i<=n-1;i++) cnt1+=num*b[i],num*=10;
		
		if(map1[cnt1]==1) return;
		ans++,map1[cnt1]=1;
		return;
	}
	a[x]=value[x],b[x]=value[x+1];dfs1(x+1);
	if(value[x]==1){
		a[x]=2,b[x]=1;dfs1(x+1);
		a[x]=2;b[x]=2;dfs1(x+1);
	}
	else{
		a[x]=1,b[x]=1;dfs1(x+1);
		a[x]=1;b[x]=2;dfs1(x+1);
	}
	return;
}
void dfs(int x){
	if(x>n){
		dfs1(1);
		return;
	}
	if(value[x]==0){
		for(int i=1;i<=v;i++){
			value[x]=i;dfs(x+1);value[x]=0;
		}
	}
	else dfs(x+1);
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T!=0){
		T--;
		scanf("%d%d%d",&n,&m,&v);
		if(n<=10&&v<=2){
			int mark1=0;
		    memset(vis,0,sizeof(vis)),memset(value,0,sizeof(value));
			for(int i=1;i<=m;i++){
			    scanf("%d%d",&c[i],&d[i]),value[c[i]]=d[i];
			    if(vis[c[i]]!=0&&vis[c[i]]!=d[i]&&mark1==0){printf("0\n"),mark1=1;}
			    vis[c[i]]=d[i];
		    }
		    if(mark1==1) continue;
			ans=0;dfs(1);
			printf("%lld\n",ans);
			continue;
		}
		else if(m==n){
//			printf("*");
			long long cnt1=0;ans=1;
			for(int i=1;i<=n;i++) scanf("%d%d",&xx,&yy);
			for(int i=1;i<=n-1;i++){
				cnt1=(1ll*(v-1)*v%mod+1)%mod;
				ans=ans*cnt1%mod;ans=(ans+mod)%mod;
			}
			printf("%lld\n",ans);
		}
		else{
			for(int i=1;i<=n;i++) scanf("%d%d",&xx,&yy);
		} 
	}
	return 0;
}
