#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=1e9+7;
inline void read(int &x){
	char ch=getchar();
	int q=1;x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			q=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	x=x*q;
	return;
}
struct limit{
	int c,d;
}arr[N];
int use[N];
int dp[N][3];
int n,m,v;

int now[N][3],res;
int cmp(){
	int ans=1;
	for(int i=1;i<n;i++){
		ans=ans*(v-1)%mod*v+1;
		ans%=mod;
	}
	return ans;
}
int cnt(){
	for(int i=1;i<n;i++){
		if(use[i]==now[i][0]&&use[i+1]!=0&&use[i+1]!=now[i][1]){
			return 0;
		}
	}
	return 1;
}
void dfs(int d){
	if(d==n){
		res=res+cnt();
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			now[d][0]=i,now[d][1]=j;
			dfs(d+1);
		}
	}
	return;
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	read(T);
	while(T--){
		read(n),read(m),read(v);
		memset(use,0,sizeof(use));
		memset(dp,0,sizeof(use));
		bool flag=1,t=0;
		for(int i=1;i<=m;i++){
			read(arr[i].c),read(arr[i].d);
			if(n>N){
				flag=0;t=1;
				continue;
			}
			if(use[arr[i].c]!=0&&use[arr[i].c]!=arr[i].d){
				flag=0;
			}
			use[arr[i].c]=arr[i].d;
		}
		if(!flag){
			if(t==1&&n==m){
				cout<<cmp()%mod<<"\n";
			}else{
				cout<<0<<"\n";
			}
			continue;
		}
		if(n<15){
			res=0;
			dfs(1);
			cout<<res<<"\n";
			continue;
		}
		if(m==n){
			cout<<cmp()%mod<<"\n";
			continue;
		}
		if(use[1]!=0){
			dp[1][1]=1,dp[1][0]=0;
		}else{
			dp[1][1]=0,dp[1][0]=1; 
		}
		for(int i=2;i<=n;i++){
			if(use[i]==0){
				dp[i][0]=dp[i-1][1]*v%mod*(v-1)+dp[i-1][0]*v%mod*v;  
				dp[i][1]=dp[i-1][1]*v;
			}else{
				dp[i][0]=0;
				if(use[i-1]==0){
					dp[i][1]=dp[i-1][0]*v%mod*v+dp[i-1][1]*v%mod*v;
				}else{
					dp[i][1]=dp[i-1][0]*v%mod*v+dp[i-1][1]*(v-1)%mod*v+1;
				}
			}
			dp[i][0]%=mod,dp[i][1]%=mod;
		}
		cout<<(dp[n][1]+dp[n][0])%mod<<"\n";
	}
	return 0;
}
