#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int N=1e6+10;
const int mod=1e9+7;

int n,m,v;
int c[N],d[N];

int a[N];
int ans,res;
int p[N],q[N];
int dfs1(int x)
{
	if(x>n)
	{
		for(int i=1;i<n;i++)
			if(a[i]==p[i]&&a[i+1]!=q[i]) return 0;
		return 1;
	}
	if(a[x]) return dfs1(x+1);
	if(a[x-1]==p[x-1])
	{
		a[x]=q[x-1];
		int get=dfs1(x+1);
		a[x]=0;
		return get;
	}
	for(int i=1;i<=v;i++)
	{
		a[x]=i;
		if(dfs1(x+1))
		{
			a[x]=0;
			return 1;
		}
	}
	a[x]=0;
	return 0;
}
void dfs2(int x)
{
	if(x>n-1)
	{
		ans+=dfs1(1),ans%=mod;
		return ;
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
		{
			p[x]=i,q[x]=j;
			dfs2(x+1);
		}
}

int A()
{
	for(int i=1;i<=n;i++)
		if(!a[i]) return 0;
	return 1;
}

void work()
{
	ans=0;
	int flg=1;
	scanf("%d%d%d",&n,&m,&v);
	a[0]=-1;
	for(int i=1;i<=n;i++) a[i]=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&c[i],&d[i]);
		if(a[c[i]]&&a[c[i]]!=d[i]) flg=0;
		a[c[i]]=d[i];
	}
	if(A())
	{
		ans=1;
		for(int i=1;i<n;i++) ans=(1ll*ans*((1ll*v*(v-1)%mod+1)%mod))%mod;
		printf("%d\n",ans);
		return ;
	}
	if(!flg) return printf("0\n"),void();
	dfs2(1);
	printf("%d\n",ans%mod);
}

int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--) work();
	return 0;
}
