#include<iostream>
#define int long long
using namespace std;
int a[114221],b[123221],x[134131],ans;
int n,m,v;
const int mod = 1e9 + 7;
bool check(){
	for(int i=1;i<n;i++){
		if(a[i]==x[i]&&b[i]!=x[i+1]&&x[i+1]!=0&&x[i]!=0){
			return false;
		}
	}
	return true;
}
void dfs(int pos){
	if(pos==n){
		if(check()){
			ans++;
			ans%=mod;
		}
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			a[pos] = i;
			b[pos] = j;
			dfs(pos+1);
		}
	}
	return;
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		ans = 0;
		bool f = 0;
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++){
			int c,d;
			cin>>c>>d;
			if(x[c]!=0){
				f = 1;
				cout<<0;
				break;
			}
			x[c] = d;
		}
		if(f==1){
			continue;
		}
		dfs(1);
		cout<<ans<<endl;
	}
	return 0;
} 
