#include<bits/stdc++.h> 
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m,v,a[114514],c[114514],d[114514],b[5145][5145],to[114514],ans;
void dfs(int x)
{
	memset(a,0,sizeof(a));
	for(int i=1;i<=m;i++)
	{
		if(a[c[i]]&&a[c[i]]!=d[i]) return ;
		a[c[i]]=d[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0) continue;
		if(to[a[i]]!=0)
		{
			if(a[i+1]==0) a[i+1]=to[a[i]];
			else if(to[a[i]]!=a[i+1]) return ;
		}
	}
	if(x==n-1) 
	{
		ans++;
		ans%=mod;
		return ;
	}
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			int tmp=to[i];
			b[i][j]=1,to[i]=j;
			dfs(x+1);
			b[i][j]=0,to[i]=tmp;
		}
	}
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	scanf("%lld",&T);
	while(T--)
	{
		ans=0;
		scanf("%lld%lld%lld",&n,&m,&v);
		for(int i=1;i<=m;i++) scanf("%lld%lld",&c[i],&d[i]); 
		dfs(0);
		printf("%lld\n",ans);
	} 
} 
