#include<bits/stdc++.h>
using namespace std;
int Tn,n,m,v,x[100010],xx[100010],a[100010],b[100010],f;
const long long Mod = 1e9+7;
long long ans;
bool chk()
{
	for(int i=1;i<=n;i++)
		xx[i] = x[i];
	for(int i=1;i<n;i++)
	{
		if(xx[i]==0)
			continue;
		if(xx[i]==a[i])
		{
			if(xx[i+1]==0)
			{
				xx[i+1]=b[i];
				continue;
			}
			if(xx[i+1]==b[i])
				continue;
			return false;
		}
	}
	return true;
}
void dfs(int cs)
{
	if(cs==n)
	{
		if(chk())
			ans = (ans+1)%Mod; 
		return ;
	}
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			a[cs] = i , b[cs] = j;
			dfs(cs+1);
		}
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	
	scanf("%d",&Tn);
	while(Tn--)
	{
		ans = 0,f=1;
		scanf("%d%d%d",&n,&m,&v);
		
		memset(x,0,sizeof(x));
		
		for(int i=1,c,d;i<=m;i++)
		{
			scanf("%d%d",&c,&d);
			if(x[c])
				f=0;
			x[c]=d;
		}
		if(f==0)
		{
			puts("0");
			continue;
		}
		if(v<=2)
			dfs(1); 
		printf("%lld\n",ans);
	}
	
	return 0;
} 
