#include<bits/stdc++.h>
using namespace std;
const long long Mod=1e9+7;
struct node{
	long long c,d;
} input[100010];
int t;
long long n,m,v,a[100010],b[100010],ans,T,tot;
map<long long,int> M;
long long _pow(long long d,long long z)
{
	long long ans=1;
	while(z){
		if(z&1)
			ans=ans*d%Mod;
		d=d*d%Mod;
		z>>=1;
	}
	return ans;
}
bool chk()
{
	int i=1,p=input[1].c;
	while(p<n&&i<m){
//		cout<<a[p]<<","<<input[i].d<<"|\n";
		if(a[p]==input[i].d){
			while(b[p]==a[p+1]&&p<input[i+1].c-1)
				p++;
//			cout<<p<<","<<b[p]<<"\n";
			if(p==input[i+1].c-1&&b[p]!=input[i+1].d)
				return false;
		}
		i++;
		p=input[i].c;
	}
	return true;
}
void dfs(int dep)
{
	if(!chk())
		return;
	if(dep>=n){
		ans++;
//		cout<<"No."<<ans<<"\n";
//		for(int i=1;i<n;i++)
//			cout<<a[i]<<" "<<b[i]<<"\n";
//		if(ans==33)
//			exit(0);
		return;
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++){
			a[dep]=i;
			b[dep]=j;
			dfs(dep+1);
		}
}
bool cmp(node q,node h)
{
	return q.c<h.c;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		bool f=false;
		M.clear();
		tot=0;
		for(int i=1;i<=m;i++){
			long long c_i,d_i;
			cin>>c_i>>d_i;
			int last_num=M[c_i];
			if(last_num!=0){
				if(last_num!=d_i)
					f=true;
			}
			else{
				M[c_i]=d_i;
				input[++tot].c=c_i;
				input[tot].d=d_i;
			}
		}
		sort(input+1,input+tot+1,cmp);
		m=tot;
		if(f){
			cout<<"0\n";
			continue;
		}
		if(m==1)
			cout<<_pow(v,2*(n-1))<<"\n";
		else if(m==n){
			cout<<_pow(1+(v-1)*v,n-1)<<"\n";
		}
		else{
			memset(a,0,sizeof(a));
			memset(b,0,sizeof(b));
			ans=0;
			dfs(1);
			cout<<ans<<"\n";
		}
	}
	return 0;
}
