#include<cstdio>
#include<iostream>
using namespace std;
#define Maxn (int)(5e5+10)
#define mod (long long)(1e9+7)
int a[Maxn],b[Maxn],c[Maxn],d[Maxn];
int x[Maxn];
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin>>T;
	while(T--){
		int n,m,v;
		scanf("%d %d %d",&n,&m,&v);
		for(int i=1;i<=m;i++){
			scanf("%d %d",&c[i],&d[i]);//di大于等于1 
		}
		if(v==2){//特殊性质1，只有两种取值1或2 
			for(int i=0;i<=n;i++){
				x[i]=0;
			}
			int chk=0;
			for(int i=1;i<=m;i++){
				if(x[c[i]]==0||x[c[i]]==d[i]) x[c[i]]=d[i];
				else{
					chk=-1;
					printf("0\n");
					break;
				}
			}
			if(chk==-1) continue;
			long long ans=1;
			int lst=0;
			if(x[1]!=0) lst=1;
			for(int i=2;i<=n;i++){
				if(x[i]!=0&&x[i-1]==0&&lst!=0){
					ans=ans%mod;
					long long res=ans;
					ans=4*res;
					ans=ans%mod;
					for(int j=1;j<(i-lst);j++){
						res/=2;
					}
					ans-=res;
					ans=ans%mod;
				}
				else if(x[i]!=0&&x[i-1]!=0){
					ans=ans%mod;
					ans=3*ans;
					ans=ans%mod;
				}
				else{
					ans=ans%mod;
					ans=4*ans;
					ans=ans%mod;
				}
				if(x[i]!=0) lst=i;
			}
			ans=ans%mod;
			printf("%lld\n",ans);
		}
		else if(m==n){
			long long ans=1;
			long long k=v*(v-1);
			k%=mod;
			k+=1;
			for(int i=1;i<=n;i++){
				ans*=k;
				ans%=mod;
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}
