#include<bits/stdc++.h>
#define int long long 
#define rep(i,a,b)	for(int i = (a);i<=(b);i++)
#define lep(i,a,b)	for(int i = (a);i>=(b);i--)	
using namespace std;
const int N = 1e6+10;
const int P = 1010;
const int M = 1e9+7;
int t,n,m,v,c[N],d[N],ans,a[N],b[N],f[N],g[N]; 
bool flagA,flagB;
inline int qpow(int a,int b){
	int c = 1;
	while(b){
		if(b&1)	c = c*a%M;
		a = a*a%M;
		b>>=1;
	}
	return c;
}
inline void dfs(int x){
	if(x>=n){
		rep(i,1,n)	g[i] = f[i];
		rep(i,1,n-1){
			if(g[i] && a[i] == g[i]){
				if(g[i+1] && g[i+1]!=b[i])	return;
				if(!g[i+1])	g[i+1] = b[i];
			}
		}
		ans++;
		return;
	}
	a[x] = 1,b[x] = 1;
	dfs(x+1);
	a[x] = 1,b[x] = 2;
	dfs(x+1);
	a[x] = 2,b[x] = 1;
	dfs(x+1);
	a[x] = 2,b[x] = 2;
	dfs(x+1); 
}
inline void solve(){
	cin>>n>>m>>v;
	ans = 0;
	rep(i,1,m)	cin>>c[i]>>d[i];
	if(n == m){
		flagA = 1;	ans = 1;
		rep(i,1,m)	if(c[i] != i)	flagA = 0;
		if(flagA){
			rep(i,1,n-1){
				ans = (ans*(1ll+(v-1)*v%M))%M;
			}
		}
		cout<<ans<<"\n";
	}
	else{
		ans = 1;
		if(m == 1){
			ans = qpow(v*v%M,n-1)%M;
		}
		else{
			ans = 0;
			rep(i,1,n)	f[i] = 0; 
			rep(i,1,m){
				if(!f[c[i]] || f[c[i]] == d[i]){
					f[c[i]] = d[i];
				}
				else{
					cout<<0<<"\n";
					return;
				}
			}
			dfs(1);
		}
		cout<<ans<<"\n";
	}
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	cin>>t;
	while(t--)	solve();
	return 0;
}
