#include<cstdio>
using namespace std;
int n,m,v,ans;
bool f;
const int N=1e5+10,Mod=1e9+7,M=20;
int c[N],d[N];
int a[M],b[M];
int x[N];
void chk(int p)
{
	if(f) return;
	if(p>n)
	{
		for(int i=1;i<=m;i++)
			if(x[c[i]]!=d[i]) return;
		for(int i=1;i<n;i++)
			if(x[i]==a[i]&&x[i+1]!=b[i]) return;
		f=true;
		return;
	}
	else
	{
		for(int i=1;i<=v;i++)
		{
			x[p]=i;
			chk(p+1);
			if(f) return;
		}
	}
	return;
}
void dfs(int k)
{
	if(k==n)
	{
		f=false;
		chk(1);
		ans=(ans+f)%Mod;
	} 
	else
	{
		for(int i=1;i<=v;i++)
			for(int j=1;j<=v;j++)
			{
				a[k]=i;
				b[k]=j;
				dfs(k+1);
			}
	}
	return;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&v);
		for(int i=1;i<=m;i++)
			scanf("%d%d",&c[i],&d[i]);
		ans=0;
		dfs(1);
		printf("ans=%d\n",ans);
	}
	return 0;
}
