#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N=1e5+5,M=1e3+5,MOD=1e9+7;

int qsm(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ans;
}

int T;
int n,m,v;
int c[N],d[N];
int bk[N];

int a[N],b[N];
int f[N][M];

int zans=0;
void dfs(int tmp){
	if(tmp>=n){
		for(int i=1;i<=n;i++) for(int j=1;j<=v;j++) f[i][j]=0;
		if(bk[1]) f[1][bk[1]]=1;
		else for(int i=1;i<=v;i++) f[1][i]=1;
		
//		for(int i=1;i<=n;i++) cout<<a[i]<<" "<<b[i]<<"\n";
		
		for(int i=2;i<=n;i++){
			if(!bk[i]){
				for(int j=1;j<=v;j++){
					if(j==a[i-1]){
						f[i][b[i-1]]|=f[i-1][j];
						continue;
					}
					for(int k=1;k<=v;k++) f[i][k]|=f[i-1][j];	
				}
			}
			else{
				for(int j=1;j<=v;j++){
					if(j==a[i-1]){
						if(b[i-1]==bk[i]) 
							f[i][b[i-1]]|=f[i-1][j];
						continue;
					}
					f[i][bk[i]]|=f[i-1][j];
				}
			}
		}
			
		int ans=0;
		for(int i=1;i<=v;i++)
			if(f[n][i]){
				ans=1;
				break;
			}
		zans+=ans;
		return;
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++){
			a[tmp]=i; b[tmp]=j;
			dfs(tmp+1);
		}
}

void Solve(){
	scanf("%lld%lld%lld",&n,&m,&v);
	for(int i=1;i<=n;i++) bk[i]=0;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&c[i],&d[i]);
		if(bk[c[i]] && bk[c[i]]!=d[i]){
			printf("0\n");
			return;
		}
		bk[c[i]]=d[i];
	}
	
	if(m==1){
		printf("%lld\n",qsm(v,2*n-2));
		return;
	}
	
	zans=0;
	dfs(1);
	printf("%lld\n",zans);
}

signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout); 
	
	scanf("%lld",&T);
	for(int i=1;i<=T;i++){
		Solve();
	}
	return 0;
}


