#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll ans;
const int mod=1e9+7;
const int N=1e3; 
int t,n,m,v;
struct zh{
	int a,b;
};
zh pa[N];
int c[N],d[N];
int mem[N];
void dfs(int p){
	if(p>=n){
		for(int i=1;i<n;i++){
			if(pa[i].a==mem[i]){
				if(!mem[i+1]){
					mem[i+1]=pa[i].b;
				}else{
					if(mem[i+1]!=pa[i].b)return;
				}
			}
		}
		memset(mem,0,sizeof(mem));
		ans++;
		ans%=mod;
//		for(int i=1;i<n;i++){
//			cout<<pa[i].a<<' '<<pa[i].b<<'\t';
//		}
//		cout<<endl;
		return;
	}
	for(int i=1;i<=v;i++){
		pa[p].a=i;
		for(int j=1;j<=v;j++){
			pa[p].b=j;
		///	cout<<pa[p].a<<' '<<pa[p].b<<endl;
			dfs(p+1);
		}
	}
}
bool istrue=1;
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--){
		ans=0;
		istrue=1;
		memset(mem,0,sizeof(mem));
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++){
			cin>>c[i];
			int temp;
			cin>>temp;
			if(mem[c[i]]&&mem[c[i]]!=temp){	
				istrue=false;
				continue;
			}
			mem[c[i]]=temp; 
		}
		if(istrue)dfs(1);
		else ans=0;
		cout<<ans<<endl;
	}
	return 0;
}
/*
1
6 5 2
4 2
5 1
4 2
2 2
2 1
7 1 2
4 1

3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2
      
4
5 1 2
1 2
6 5 2
4 2
5 1
4 2
2 2
2 1
7 1 2
4 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

*/
