#include<bits/stdc++.h>
using namespace std;
#define int long long
#define L(i,l,r) for(int i=l;i<=r;i++)
#define R(i,r,l) for(int i=r;i>=l;i--)

const int N=1e6+10,M=1e5+10,MOD=1e9+7;

int n,m,v,ans;
int x[N],a[N],b[N];
bool check(){
	static int xx[N];
	L(i,1,n) xx[i]=x[i]; 
	L(i,1,n-1){
		if(xx[i]==a[i]){
			if(!xx[i+1]){
				xx[i+1]=b[i];
			}else if(xx[i+1]!=b[i]){
				return false;
			}
		}
	}
	return true;
}
void dfs(int u){
	if(u==n){
		if(check()){
			ans=(ans+1)%MOD; 
		}
		return;
	}
	L(i,1,v){
		a[u]=i;
		L(j,1,v){
			b[u]=j;
			dfs(u+1);
		} 
 	}	
}
void solve(){
	ans=0;
	cin>>n>>m>>v;
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	memset(x,0,sizeof x);
	bool f=false;
	L(i,1,m){
		int c,d;
		cin>>c>>d;
		if(!x[c]) x[c]=d;
		else if(x[c]!=d){
			f=true;
		} 
	}
	if(f){
		cout<<0<<'\n';
		return;
	}
	dfs(1);
	cout<<ans<<'\n';
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin>>T; 
	while(T--) solve();
	return 0;
}
