#include<bits/stdc++.h>
#define ll long long
#define R register
using namespace std;
const int N=1e5+5,mod=1e9+7;
inline ll qmul(ll x,int y){
	ll res=1;
	while(y){
		if(y&1)res=res*x%mod;
		y>>=1;x=x*x%mod;
	}
	return res;
}
struct node{int x,y;};
ll c[N],d[N],n,m,V,tot,ans;
int aa[N],bb[N],x[N];
vector<node> v;
inline bool chk(){
	for(R int i=1;i<=n;++i)x[i]=0;
	for(R int i=0;i<m;++i)x[v[i].x]=v[i].y;
	for(R int i=1;i<n;++i){
		if(x[i]){
			if(x[i]==aa[i]){
				if(x[i+1]&&x[i+1]!=bb[i])return 0;
				else x[i+1]=bb[i];
			}
		}
	}
	return 1;
}
inline void dfs(int st){
	if(st>=n){
		if(chk()){
			ans=(ans+1)%mod;
//			for(R int i=1;i<n;++i){
//				cout<<aa[i]<<' '<<bb[i]<<'\n';
//			}
		}
		return; 
	}
	for(R int i=1;i<=V;++i){
		for(R int j=1;j<=V;++j){
			aa[st]=i;bb[st]=j;
			dfs(st+1);
		}
	}
}
inline void solve(){
	cin>>n>>m>>V;
	v.clear();
	for(R int i=1;i<=m;++i){
		int x,y;cin>>x>>y;
		v.emplace_back(node{x,y});
	}
	sort(v.begin(),v.end(),[&](node x,node y){return x.x<y.x;});
	for(R int i=1;i<m;++i){
		if(v[i].x==v[i-1].x&&v[i].y!=v[i-1].y){
			return cout<<"0\n",void();
		}
	}
	for(R int i=0;i<m;++i){
		++tot;
		if(i&&v[i].x==v[i-1].x)--tot;
	}
	if(tot==n){
		ll res=1;
		for(R int i=1;i<n;++i){
			res=(res*((V-1)*V%mod+1)%mod)%mod;
		}
		cout<<res<<'\n';
		return;
	}else if(tot==1){
		ll res=qmul(V,(n-1)*2);
		cout<<res<<'\n';
	}else{
		ans=0;
		dfs(1);
		cout<<ans<<'\n';
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int _;cin>>_;while(_--)solve();
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

4
3
0
*/
/*
5
5 1 2
1 2
6 5 2
4 2
5 1
4 2
2 2
2 1
7 1 2
4 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
12 2 2
7 2
7 2

256
0
4096
129600
4194304
*/
