#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm=100004;
const ll mod=1e9+7;
ll qpow(ll x,ll k){
	ll res=1;
	while(k){
		if(k&1)res=res*x%mod;
		x=x*x%mod,k>>=1;
	}
	return res;
}
int _;
int n,m,v;
struct node{
	int c,d;
	bool operator <(const node &qyy)const{return c<qyy.c;}
	bool operator ==(const node &qyy)const{return (c==qyy.c&&d==qyy.d);}
}lm[maxm];
ll ans;
void solveA(){//goal!
	ans=1ll;
	for(int i=1;i<n;i++)
		ans=ans*(1ll*(v-1)*v%mod+1)%mod;
}
void solvem_1(){
//	ans=1ll;
	ans=qpow(1ll*v*v%mod,n-1);
}
int a[maxm],b[maxm];
int mst[maxm];
ll dfs(int dep){
	if(dep==n){
		int nw=-1;
		for(int i=1;i<=n;i++){
			if(nw==a[i]) nw=b[i];
			else nw=-1;
			if(mst[i]){
				if(~nw&&nw!=mst[i]) return 0;
				nw=mst[i];
			}
		}
		return 1;
	}
	ll res=0;
	a[dep+1]=0;b[dep+1]=0;
	res=(res+dfs(dep+1))%mod;
	b[dep+1]=1;
	res=(res+dfs(dep+1))%mod;
	a[dep+1]=1;
	res=(res+dfs(dep+1))%mod;
	b[dep+1]=0;
	res=(res+dfs(dep+1))%mod;
	return res;
}
int main(){
//	freopen("assign2.in","r",stdin);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>_;
	while(_--){
		cin>>n>>m>>v;
		bool A_=(n==m);
		for(int i=1;i<=m;i++){
			cin>>lm[i].c>>lm[i].d;
			if(lm[i].c!=i) A_=0;
		} 
		if(m==1){//solve!
			solvem_1();
			cout<<ans<<'\n';
			continue;
		}
		else if(A_){//solve!
			solveA();
			cout<<ans<<'\n';
			continue;
		}
		else if(v<=2){
			for(int i=1;i<=n;i++) mst[lm[i].c]=0;
			bool kk=0;
			for(int i=1;i<=m;i++){
				if(mst[lm[i].c]&&mst[lm[i].c]!=lm[i].d){
					cout<<0<<'\n';
					kk=1;
					break;
				}
				mst[lm[i].c]=lm[i].d;
			} 
			if(!kk) cout<<dfs(0)<<'\n';
			continue;
		}
		cout<<0<<'\n';
	}
	return 0;
}
/*
1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2
*/
