#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline ll read() {
	ll res=0,f=0;
	char c;
	do {
		c=getchar();
		f|=c=='-';
	} while(!isdigit(c));
	do {
		res=(res<<1)+(res<<3)+(c^48);
		c=getchar();
	} while(isdigit(c));
	return f?-res:res;
}

void write(ll x) {
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+48);
}

const ll N=1e6+10,MOD=1e9+7;

ll T,n,m,v,c[N],d[N],a[N],s[N],nxt[N<<4],ans;

bool flagA,flagB,flag,flag1;

inline void init() {
	memset(a,0,sizeof a);
	memset(nxt,0,sizeof nxt);
	memset(c,0,sizeof c);
	memset(d,0,sizeof d);
	flagA=false,flagB=false,flag=false;
}

void dfs(ll k) {
	if(flag1) return ;
	if(k==n) {
		ans++;
		return ;
	}
	if(nxt[a[k]]&&a[k+1]&&a[k+1]!=nxt[a[k]]) {
		flag1=true;
		return ;
	}
	for(ll i=1; i<=v; i++) {
		a[k+1]=i;
		dfs(k+1);
	}
}

inline void work1() {
	for(ll i1=1; i1<=n; i1++) {
		for(ll i=1; i<=v; i++) {
			for(ll j=1; j<=v; j++) {
				flag1=false;
				for(ll k=1; k<=n; k++) a[k]=s[k];
				nxt[i]=j;
				dfs(1);
				nxt[i]=0;
			}
		}
	}
	write(ans);
	putchar('\n');
}

ll mypow(ll x,ll y) {
	if(y==0) return 1;
	if(y==1) return x%MOD;
	ll res=mypow(x,y/2)%MOD;
	if(y&1) return x%MOD*res%MOD*res%MOD;
	else return res%MOD*res%MOD;
}

inline void work2() {
	v%=MOD;
	ll cifang=2*n-2;
	cifang%=MOD;
	write(mypow(v,cifang));
	putchar('\n');
}

inline void workA() {

}

inline void workB() {

}

inline void work() {
	T=read();
	while(T--) {
		init();
		n=read(),m=read(),v=read();
		if(m==1) {
			ll x=read(),y=read();
			work2();
			continue;
		}
		for(ll i=1; i<=m; i++) {
			c[i]=read(),d[i]=read();
			if(c[i]&&s[c[i]]&&s[c[i]]!=d[i])
				flag=true;
			s[c[i]]=d[i];
			if(c[i]!=i) flagA=true;
			if(d[i]!=1) flagB=true;
		}
		if(flag) {
			putchar('0');
			putchar('\n');
			continue;
		}

		if(v<=2) {
			work1();
			continue;
		}

		if(!flagA) {
			workA();
			continue;
		}
		if(!flagB) {
			workB();
			continue;
		}
	}
}

int main() {
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
