#include<iostream>
#include<cstring>
#include<map>
using namespace std;
map<int,int>xx;
int n,v;
int l[100005];
int a[100005],b[100005],ans;
const int Mod=1e9+7;
long long qpow(long long a,long long b){
	long long ans=1;
	while(b){
		if(b%2)ans*=a,ans%=Mod;
		b/=2,a*=a,a%=Mod;
	}
	return ans%Mod;
}
bool dfs(int x){
	if(x==n+1){
		for(int i=1;i<n;i++)if(l[i]==a[i]&&l[i+1]!=b[i])return 0;
		return 1;
	}
	if(xx[x]!=0){
		l[x]=xx[x];
		if(dfs(x+1))return 1;
		return 0;
	}
	for(int i=1;i<=v;i++){
		l[x]=i;
		if(dfs(x+1))return 1;
		l[x]=0;
	}
	return 0;
}
void dfs2(int x){
	if(x==n){
		if(dfs(1))ans++;
		return;
	}
	for(int i=1;i<=v;i++)for(int j=1;j<=v;j++){
		a[x]=i,b[x]=j;
		dfs2(x+1);
		a[x]=0,b[x]=0;
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin>>T;
	while(T--){
		xx.clear();
		int m;
		cin>>n>>m>>v;
		int sm=0;
		bool f=0;
		for(int i=1;i<=m;i++){
			int c,d;
			cin>>c>>d;
			if(xx[c]!=0&&xx[c]!=d){
				f=1;
			}
			if(xx[c]==d)sm--;
			xx[c]=d;
			sm++;
		}
		if(f){
			cout<<0<<endl;
			continue;
		}
		if(sm==1){
			cout<<qpow(v,n*2-2)<<endl;
			continue;
		}
		ans=0;
		//cout<<1<<endl;
		dfs2(1);
		cout<<ans<<endl;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
