#include<bits/stdc++.h>
using namespace std;
#define ll long long
void file(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
}
int re(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define int ll
const int N = 1e5+10,MOD = 1e9+7;
int n,m,v,a[N],b[N];
struct node{
	int c,d;
	friend bool operator == (node a,node b){
		return a.c==b.c&&a.d==b.d;
	}
}c[N];
int Pow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
int ans=0;
void check(){
	for(int i=1;i<m;i++){
		if(a[c[i].c]==c[i].d){
			int flag=1;
			for(int j=c[i].c+1;j<c[i+1].c;j++){
				if(a[j]!=b[j-1]){
					flag=0;
					break;
				}
			}
			if(b[c[i+1].c-1]!=c[i+1].d&&flag)return;
		}
	}
	ans++;
}
void dfs(int id){
	if(id==n){
		check();
		return;
	}
	for(int i=1;i<=v;i++){
		a[id]=i;
		for(int j=1;j<=v;j++){
			b[id]=j;
			dfs(id+1);
		}
	}
}
/*
1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2
129600
*/
bool cmp(node a,node b){
	return a.c<b.c;
}
signed main(){
	file();
	int QWQ=re();while(QWQ--){
		n=re(),m=re(),v=re();for(int i=1;i<=m;i++)c[i]={re(),re()};
		sort(c+1,c+m+1,cmp);
		int Z=0;
		m=unique(c+1,c+m+1)-c-1;
		for(int i=1;i<=m;i++){
			if(c[i].c==c[i-1].c){
				puts("0");
				Z=1;
				break;
			}
		}
		if(Z)continue;
		ans=Pow(v*v%MOD,n-1);
		if(m==1){
			cout<<ans<<"\n";
			continue;
		}
		ans=0;dfs(1);
		cout<<ans<<"\n";
	}
	return 0;
}
