#include<cstdio>
#include<iostream>
#include<cstring>
#define re register
using namespace std;
const int M=1e9+7;
int T,n,m,v,ans;
int a[15],bz[15][15];
inline int ksm(re int x,re int y)
{
	re int res=1;
	while(y)
	{
		if(y&1) res=(res*x)%M;
		x=x*x%M;
		y>>=1;
	}
	return res;
}
inline void pailie(re int x)
{
	if(x==n+1)
	{
		for(re int i=1;i<=v;++i)
		{
			for(re int j=1;j<=v;++j)
			{
				re bool flag=true;
				for(re int k=1;k<n;++k)
				{
					if(a[k]==i&&a[k+1]==j){flag=false;break;}
				}
				if(flag==true&&bz[i][j]==0){++ans;bz[i][j]=1;}
			}
		}
	}
	else
	{
		if(!a[x])
		{
			for(re int i=1;i<=v;++i)
			{
				a[x]=i;
				pailie(x+1);
			}
		}
		else pailie(x+1);
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&v);
		re bool flag=true;
		for(re int i=1;i<=n;++i)
			a[i]=0;
		for(re int i=1;i<=m;++i)
		{
			re int x,y;
			scanf("%d%d",&x,&y);
			if(!a[x]||a[x]==y) a[x]=y;
			else flag=false;
		}
		if(flag==false){printf("0\n");continue;}
		if(n<=12)
		{
			ans=0;
			memset(bz,0,sizeof(bz));
			pailie(1);
			printf("%d\n",ksm(ans,n-1));
		}
	}
	return 0;
}
