#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,v,zhi[10010],ans=0,e[10010],f[10010],a[10010];
bool check(long long num)
{
	if(num==n+1)
	{
		for(long long i=1;i<n;i++)
		{
			if(a[i]==e[i])
			{
				if(a[i+1]!=f[i])
				{
					return false;
				}
			}
		}
		return true;
	}
	if(zhi[num]!=0)
	{
		a[num]=zhi[num];
		if(check(num+1))
		{
			return true;
		}
	}
	else
	{
		for(a[num]=1;a[num]<=v;a[num]++)
		{
			if(check(num+1))
			{
				return true;
			}
		}
	}
	return false;
}
void dfs(long long num)
{
	if(num==n)
	{
		ans+=check(1);
		return;
	}
	for(e[num]=1;e[num]<=v;e[num]++)
	{
		for(f[num]=1;f[num]<=v;f[num]++)
		{
			dfs(num+1);
		}
	}
	return;
}
void subtask1()
{
	ans=0;
	for(long long i=1;i<=n;i++)
	{
		zhi[i]=0;
	}
	bool flag=false;
	for(long long i=1;i<=m;i++)
	{
		long long c,d;
		scanf("%lld%lld",&c,&d);
		if(zhi[c]!=0&&zhi[c]!=d)
		{
			puts("0");
			flag=true;
			return;
		}
		zhi[c]=d;
	}
	dfs(1);
	printf("%lld\n",ans);
}
long long ksm(long long num,long long su)
{
	long long now=num,ret=1;
	while(su)
	{
		if(su%2==1)
		{
			ret*=now;
			ret%=mod;
		}
		now*=now;
		now%=mod;
		su>>=1;
	}
	return ret;
}
void subtask2()
{
	for(long long i=1;i<=m;i++)
	{
		long long c,d;
		scanf("%lld%lld",&c,&d);
	}
	printf("%lld\n",ksm(v*v%mod,n-1));
	return;
}
void solve()
{
	scanf("%lld%lld%lld",&n,&m,&v);
	if(m==1)
	{
		subtask2();
		return;
	}
	subtask1();
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	long long T;
	scanf("%lld",&T);
	while(T--)
	{
		solve();
	}
}
