#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],b[1000005],c[100005],d[100005],aa[1000005],bb[1000005],bz;
long long v,ans;
const int p=1e9+7;
unordered_map<int,int> ap;
void df(int x)
{
	if(bz)
		return;
	if(x==n+1)
	{
		bz=1;
		return;
	}
	if(x>1&&b[x-1]==aa[x-1])
	{
		if(a[x])
		{
			if(a[x]==bb[x-1])
				b[x]=a[x],df(x+1);
		}
		else
		{
			b[x]=bb[x-1],df(x+1);
		}
	}
	else
	{
		if(a[x])
		{
			b[x]=a[x],df(x+1);
		}
		else
		{
			for(int i=1;i<=v;i++)
				if(i!=aa[x])
				{
					b[x]=i,df(x+1);
					break;
				}
		}
	}
}
void dfs(int x)
{
	if(x==n)
	{
		bz=0;
		df(1);
		ans=(ans+bz)%p;
		return; 
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
			aa[x]=i,bb[x]=j,dfs(x+1);
}
long long ksm(long long x,int y)
{
	if(!y)
		return 1;
	long long g=ksm(x,y>>1);
	if(!(y&1))
		return g*g%p;
	return g*g%p*x%p; 
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int z=0;
		ans=0;
		scanf("%d%d%lld",&n,&m,&v);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&c[i],&d[i]);
			if(ap[c[i]]&&ap[c[i]]!=d[i])
				z=1;
			ap[c[i]]=d[i];
		}
		ap.clear();		
		if(z)
		{
			printf("0\n");
			continue;
		}
		if(m==1)
		{
			printf("%lld\n",ksm(v,n-1)*ksm(v,n-1)%p);
			continue;
		}
		if(n<=12&&m<=12&&v<=2)
		{
			for(int i=1;i<=m;i++)
				a[c[i]]=d[i];
			dfs(1);
			printf("%lld\n",ans);
			for(int i=1;i<=n;i++)
				a[i]=0;
			continue;
		}
		printf("%lld\n",ksm(v,n-1)*ksm(v,n-1)%p);
	}
	return 0;
}
