#include<bits/stdc++.h>
using namespace std;
#define int long long
const int P=1e9+7;
const int N=1e5+5;
int x[N],a[N],b[N],c[N],n,m,v,T,cnt,flag;
void dfs(int step)
{
	if(step==n)
	{
		for(int i=1;i<=n-1;++i)
		{
			if(x[i]==a[i])
			{
				if(x[i+1]==0) continue;
				if(x[i+1]==b[i]) continue;
				return; 
			}
		}
		cnt++;	
		return;	
	}
	for(int i=1;i<=v;++i)
	{
		for(int j=1;j<=v;++j)
		{
			a[step]=i,b[step]=j;
			dfs(step+1);
		}
	}
	return;
}
void cas1()
{
	cnt=0;
	dfs(1);
	cout<<cnt<<'\n';
}
void init()
{
	cin>>n>>m>>v;
	memset(x,0,sizeof(x));
	for(int i=1;i<=m;++i) 
	{
		int X,Y;
		cin>>X>>Y;
		if(x[X]!=0&&x[X]!=Y)
		flag=1; 
		x[X]=Y;	
	}	
}
void cas2()
{
	cnt=1;
	for(int i=1;i<=n-1;++i) cnt=(cnt%P*((v%P)*(v%P)))%P;
	cout<<cnt<<'\n';
	return; 
}
signed main()
{
	ios::sync_with_stdio(false)	;
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);

	cin>>T;
	while(T--)
	{
		flag=0;
		init();
		if(flag==1) 
		{
			cout<<0<<'\n';
			continue;
		}
		if(v<=2)cas1();
		else
		{
			cas2();
		}
	}
	return 0;
} 
