#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define N 100010
#define P 1000000007
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
int qpow(int k,int b){
	int ret=1;
	while(b){
		if(b&1)ret=1ll*ret*k%P;
		k=1ll*k*k%P,b>>=1;
	}
	return ret;
}
pair<int,int>pr[N];
int n,m,v,c[N],val[N];
#define _ 2010
int f[_][_],g[_];
//int all;
void solve(){
//	printf("all %d\n",++all);
	memset(g,0,sizeof(g)),memset(f,0,sizeof(f));
	memset(val,0,sizeof(val));
	n=read(),m=read(),v=read();
	for(int i=1;i<=m;i++)
		pr[i].fi=read(),pr[i].se=read();
	sort(pr+1,pr+1+m);
	int o=m;m=0;
	for(int i=1;i<=o;i++){
		if(pr[i].fi!=pr[i+1].fi)c[++m]=pr[i].fi;
		else if(pr[i].se!=pr[i+1].se)
			return puts("0"),void();
	}
//	printf("howd? m %d\n",m);
	if(m==1){
		printf("%d\n",qpow(v,2*(n-1)));
		return;
	}
	for(int i=1;i<m;i++){
		g[c[i]-1]=qpow(v,2*(c[i]-1));
		for(int ti=1;ti<=m;ti++)
			for(int tj=ti+1;tj<=m;tj++)
				if(c[tj]-1<=c[i]-1)
					g[c[i]-1]=((g[c[i]-1]+P-1ll*f[ti][tj]*qpow(v,2*(c[i]-1-c[tj]+1)))%P+P)%P;
		for(int j=i+1;j<=m;j++)
			f[i][j]=1ll*g[c[i]-1]*(v-1)%P*qpow(v,(c[j]-j)-(c[i]-i))%P;/*2*(n-c[j])+*/
	}
	g[n-1]=qpow(v,2*(n-1));
	for(int ti=1;ti<=m;ti++)
			for(int tj=ti+1;tj<=m;tj++)
				(g[n-1]+=(P-1ll*f[ti][tj]*qpow(v,2*(n-1-c[tj]+1))))%=P;
	printf("%d\n",g[n-1]);
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T=read();
	while(T--)solve();
	
	return 0;
}
