#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll mod=1e9+7;
int t,n,m;
ll v;
int a[N],cur[N];
ll ksm(ll x,ll e)
{
		if(e==0)
		return 1;
	ll res=1;
	while(e)
	{
			if(e&1)
			res=res*x%mod;
		e>>=1;
		x=x*x%mod;
	}
	return res%mod;
}
/*
ll fac[N],ifac[N];
void init()
{
	fac[0]=1;
	for(int i=1;i<=N-5;i++)
	{
		fac[i]=fac[i-1]*i%mod;
	}
	ifac[N-5]=ksm(fac[N-5],mod-2);
	for(int i=N-6;i>=0;i--)
	{
		ifac[i]=ifac[i+1]*(i+1)%mod;
	}
}
ll C(int All,int Sub)
{
	if(Sub>All)
		return 0;
	return fac[All]*ifac[Sub]%mod*ifac[All-Sub]%mod;
}*/
ll ans=0;
int ra[N],rb[N];
void chk()
{
		for(int i=1;i<=n;i++)
	{
			cur[i]=a[i];
	}
	bool acce=true;
	for(int i=1;i<n;i++)
	{
			if(cur[i]==ra[i])
		{
				if(!cur[i+1])
			{
					cur[i+1]=rb[i];
			}
			else if(cur[i+1]!=rb[i])//is not 0 or b_i
			{
				acce=false;
				break;
			}
		}
	}
//	for(int i=1;i<n;i++)
//	{
//		printf("(%d,%d) ",ra[i],rb[i]);
//	}
//	printf("\n");
	if(acce)
	{
		ans=(ans+1)%mod;
	}
	return; 
}
void sol(int cur)
{
	if(cur>=n)
	{
		chk();
		return;
	}
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			ra[cur]=i;
			rb[cur]=j;
			sol(cur+1);
		}
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
//	init();
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%lld",&n,&m,&v);
		if(m==1)
		{
			int tmp=0;
			scanf("%d%d",&tmp,&tmp);
			ll tot=v*v%mod;
			printf("%lld\n",ksm(tot,n-1));
			continue;
		}
		if(n>N)
		{
			printf("0\n");
			continue;
		}
		for(int i=1;i<=n;i++)
		{
			a[i]=0;
		}
		bool acr=false;
		for(int i=1;i<=m;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			if(a[x]==y)
				continue;
			if(a[x])
				acr=true;
			a[x]=y;
		}
		if(acr)
		{
			printf("0\n");
			continue;
		}
		if(m==n)
		{
			ll tot=0;
			tot=((v*v%mod-v+mod)%mod+1%mod);
			printf("%lld\n",ksm(tot,n-1));
			continue;
		}
		ans=0;
		sol(1);
		printf("%lld\n",ans);
	}
}

