#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define int long long
#define F(i,j,k) for(int i=j;i<=k;i++)
const int N=1e5+5,Mod=1e9+7;
int T,n,m,v;
bool vis[N];
int x[N],ans,a[N],b[N];
bool dfs(int id){
	if(id==n+1) return 1;
	bool flag=0;
	if(vis[id]) return dfs(id+1);
	for(int i=1;i<=v;i++){
		if(i==a[id]){
			x[id]=i;
			if(vis[id+1]&&x[id+1]!=b[id]) continue;
			flag|=dfs(id+1);
		}
		else{
			x[id]=i;
			flag|=dfs(id+1);
		}
	}return flag;
}
void deal(int id){
	if(id==n+1){
		if(dfs(1)) ans++;
		if(ans>Mod) ans-=Mod;
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			a[id]=i,b[id]=j;
			deal(id+1);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		ans=0;
		memset(vis,0,sizeof vis);
		for(int i=1;i<=m;i++){
			int c,d;
			cin>>c>>d;
			x[c]=d;vis[c]=1;
		}
		dfs(1);
		cout<<ans<<'\n';
	}
	return 0;
}

