#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e6+2;
const ll mod=1e9+7;
ll n,m,v;
ll qpow(ll A,ll B){
	A=(A+mod)%mod;
	ll res=1;
	while(B){
		if(B&1)res=res*A%mod;
		A=A*A%mod;
		B>>=1;
	}
	return res;
}
namespace sub1{
	int a[N],b[N],val[N],flag[N];
	int val1[N],flag1[N];
	ll ans;
	void dfs2(int x){
		if(x>=n){
			for(int i=1;i<=n;++i)val1[i]=val[i],flag1[i]=flag[i];
			for(int i=1;i<n;++i){
				if(a[i]==val1[i]&&flag1[i]==1){
					if(flag1[i+1]==1&&val1[i+1]!=b[i])return ;
					val1[i+1]=b[i],flag1[i+1]=1;
				}
			}
			ans=(ans+1)%mod;
			return ;
		}
		b[x]=1;
		dfs2(x+1);
		b[x]=2;
		dfs2(x+1);
	}
	void dfs(int x){
		if(x>=n){
			dfs2(1);
			return ;
		}
		a[x]=1;
		dfs(x+1);
		a[x]=2;
		dfs(x+1);
	}
	void solve(){
		for(int i=1;i<=n;++i)flag[i]=0,val[i]=0;
		int ok=0;
		for(int i=1;i<=m;++i){
			int c,d;cin>>c>>d;
			if(flag[c]&&d!=val[c])ok=1;
			val[c]=d;
			flag[c]=1;
		}
		if(ok){cout<<"0\n";return ;}
		ans=0;
		dfs(1);
		cout<<ans<<'\n';
	}
}
ll dg(ll x){
	if(x==1)return 1;
	else return ((v-1)*qpow(v,2ll*x-3)%mod+v*dg(x-1)%mod)%mod;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--){
		cin>>n>>m>>v;
		if(v<=2){
			sub1::solve();
			continue;
		}
		if(m==1){
			int cj,dj;cin>>cj>>dj;
			cout<<(qpow(v,2*(cj-1))*dg(n-cj+1)%mod+mod)%mod<<'\n';
			continue;
		}
		if(n==m){
			for(int i=1;i<=m;++i){int cj,dj;cin>>cj>>dj;}
			cout<<(qpow(v*(v-1)%mod+1,n-1)+mod)%mod<<'\n';
			continue;
		}
	}
	return 0;
}
