#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
mt19937 rnd(time(0));
ll T,n,m,v,c[100001],d[100001],x[1000001],a[1000001],b[1000001],ans;
bool f[10001],flag;
inline ll read()
{
	ll s=0,f=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
	for(;isdigit(ch);ch=getchar()) s=(s<<3)+(s<<1)+(ch^48);
	return f?-s:s;
}
void dfs3(ll k)
{
	if(flag) return;
	if(k>n)
	{
		flag=1;
		return;
	}
	if(f[k])
	{
		if(x[k-1]==a[k-1] && x[k]!=b[k-1] && k>1) return;
		dfs3(k+1);
		return;
	}
	if(x[k-1]==a[k-1])
	{
		x[k]=b[k-1];
		dfs3(k+1);
		return;
	}
	for(ll i=1;i<=v;i++)
	{
		x[k]=i;
		dfs3(k+1);
	}
}
void dfs2(ll k)
{
	if(k>=n)
	{
//		for(ll i=1;i<n;i++) cout<<b[i]<<" ";
//		cout<<"\n\n";
		flag=0;
		dfs3(1);
		if(flag) ans++;
		if(ans>mod) ans-=mod;
		flag=0;
//		cout<<"\n";
		return; 
	}
	for(ll i=1;i<=v;i++)
	{
		b[k]=i;
		dfs2(k+1);
	}
}
void dfs1(ll k)
{
	if(k>=n)
	{
//		for(ll i=1;i<n;i++) cout<<a[i]<<" ";
//		cout<<"\n";
		dfs2(1);
		return;
	}
	for(ll i=1;i<=v;i++)
	{
		a[k]=i;
		dfs1(k+1);
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	T=read();
	while(T--)
	{
		for(ll i=1;i<=n;i++)
		{
			x[i]=a[i]=b[i]=0;
		}
		for(ll i=1;i<=m;i++) f[c[i]]=0;
		ans=0;
		n=read();
		m=read();
		v=read();
		for(ll i=1;i<=m;i++)
		{
			c[i]=read();
			d[i]=read();
			x[c[i]]=d[i];
			if(!f[c[i]]) f[c[i]]=1;
			else
			{
				flag=1;
				break;
			}
		}
		if(flag)
		{
			cout<<"0\n";
			continue;
		}
		if(n>100)
		{
			cout<<rnd()%mod<<"\n";
			continue;
		}
		dfs1(1);
		cout<<ans<<"\n";
	}
	return 0;
}
