#include <cstdio>

typedef long long ll;

const int N=1e2+10;
const int mod=1e9+7;

int val[N],a[N],b[N];
bool lim[N];
ll ans;ll n,m,v;

void dfs(int u) {
	if(u==n) {
		bool fl=true;
		for(int i=1;i<=n;i++) {
			if(lim[i]) {
				if(i>=2 && val[i-1]==a[i-1] && val[i]!=b[i-1]) fl=false;
				continue;
			}
			if(val[i-1]==a[i-1]) {val[i]=b[i-1];continue;}
			val[i]=a[i]==1?a[i]+1:a[i]-1;
		}
		if(fl) ans=(ans+1)%mod;
		return;
	}
	for(int i=1;i<=v;i++) {
		for(int j=1;j<=v;j++) {
			a[u]=i,b[u]=j;
			dfs(u+1);
		}
	}
}

ll qpow(ll a,ll b) {
	ll res=1;
	while(b) {
		if(b&1) res=res*a%mod;
		a=a*a%mod;b>>=1;
	}
	return res;
}

void sol() {
	scanf("%lld%lld%lld",&n,&m,&v);
	if(m==1 || n>N-10) {
		for(int i=1,c,d;i<=m;i++) scanf("%d%d",&c,&d);
		printf("%lld\n",qpow(v,2ll*(n-1)));
		return;
	}
	bool fl=true;ans=0;
	for(int i=1;i<=n;i++) {lim[i]=false;val[i]=a[i]=b[i]=0;}
	for(int i=1,c,d;i<=m;i++) {
		scanf("%d%d",&c,&d);
		if(lim[c] && val[c]!=d) fl=false;
		lim[c]=true;val[c]=d;
	}
	if(!fl) {puts("0");return;}
	dfs(1);printf("%lld\n",ans);
}

int main() {
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout); 
	int T=0;scanf("%d",&T);
	while(T--) sol();
	return 0;
}
