// B assign
#include<bits/stdc++.h>

using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
int T,n,m,v;
int c[N],d[N];
unordered_map<int,int>mp;
bool flga,have_sol,flgv,flgm;
ll qsm(ll a,ll k){
	ll res=1;
	a%=mod;
	while(k){
		if(k&1)res=res*a%mod;
		k>>=1;
		a=a*a%mod;
	}
	return res;
}
namespace spe{
	const int speN=16;
	int x[speN];
	int a[speN],b[speN];
	ll ans=0;
	void sasolve(){
		ans=0;
		ans=1LL*v*(v-1)%mod+1;
		ans=qsm(ans%mod,n-1);
		cout<<ans<<'\n';
		return;
	}
	bool check(){
		for(int i=1;i<n;i++)
			if(x[i]==a[i]&&x[i+1]&&x[i+1]!=b[i])return false;
		return true;
	}
	void dfs(int u){
		if(u==n){
			if(check())ans++;
			return;
		}
		a[u]=1,b[u]=1;
		dfs(u+1);
		a[u]=1,b[u]=2;
		dfs(u+1);
		a[u]=2,b[u]=1;
		dfs(u+1);
		a[u]=2,b[u]=2;
		dfs(u+1);
	}
	void svsolve(){
		ans=0;
		memset(x,0,sizeof x);
		for(int i=1;i<=m;i++)
			x[c[i]]=d[i];
		dfs(1);
		cout<<ans%mod<<'\n';
		return;
	}
	void smsolve(){
		ans=0;
		ans=qsm(v*v%mod,n-2);
		ll mis=0;
		mis=v*(v-1)+1;
		mis%=mod;
		ans=ans*mis%mod;
		cout<<ans%mod<<'\n';
		return;
	}
}
void solve(){
	cin>>n>>m>>v;

	flga=true,have_sol=true,flgv=true,flgm=true;

	if(m!=1)flgm=false;
	if(n!=m)flga=false;
	if(v>2)flgv=false;
	
	mp.clear();
	for(int i=1;i<=m;i++){
		cin>>c[i]>>d[i];
		if(mp.count(c[i])&&mp[c[i]]!=d[i])have_sol=false;
		else mp[c[i]]=d[i];
		if(c[i]!=i)flga=false;
	}
	if(!have_sol){
		cout<<"0\n";
		return;
	}
	if(flga){
		spe::sasolve();
		return;
	}
	if(m==1){
		spe::smsolve();
		return;
	}
	if(v<=2){
		spe::svsolve();
		return;
	}
	cout<<"0\n";
	return;
}

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

