#include<bits/stdc++.h>
#define P pair<int,int>
#define int long long
using namespace std;
bool MB1;
const int N=1e5+10,MOD=1e9+7;
int n,m,v;
int D[N],cnt;
int s[N];
map<int,int> num;
int fast_pow(int x,int num){
	x%=MOD;
	int ans=1;
	while(num){
		if(num&1) ans=(ans*x)%MOD;
		x=(x*x)%MOD;
		num>>=1;
	}
	return ans;
}
void solve1(){
	sort(s+1,s+1+cnt);
	D[0]=1;
	for(int i=1;i<=m+1;i++) D[i]=((v*D[i-1]%MOD*(v-1)%MOD+D[i-1])%MOD)%MOD;
	int old=1,ans=1;
	for(int i=1;i<=cnt;i++){
		int ds=i;
		while(s[i+1]==s[i]+1) i++;
		ans=(ans*fast_pow(v*v%MOD,s[ds]-1-old+1)%MOD);
		//cout<<i<<" "<<ans<<endl;
		if(s[i]!=n)ans=(ans*D[i-ds]%MOD);
		else ans=(ans*D[i-ds]%MOD);
		//cout<<ans<<endl;
		old=s[i];
	}
	if(s[cnt]!=n)ans=(ans*fast_pow(v*v%MOD,n-s[cnt])%MOD);
	cout<<ans<<endl;
	num.clear();	
}
P e[N],st[N];
int ans=0,top;
void dfs(int cnt){
	if(cnt==n-1){
		bool f=1;
		for(int i=1;i<=n-1;i++){
			int x=e[i].first,y=e[i].second;
			if(!num[i]||num[i]!=x) ;
			else if(!num[i+1]) num[i+1]=y,st[++top]={i+1,y};
			else if(num[i+1]!=y) f=0;
		}
		for(int i=1;i<=top;i++) num[st[i].first]=0;
		top=0;
		ans+=f;
		return ;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			e[cnt+1]={i,j};
			dfs(cnt+1);
		}
	}
}
void solve2(){
	ans=0;
	dfs(0);
	num.clear();
	cout<<ans<<endl;
}
void solve3(){
	cout<<fast_pow(v*v%MOD,n-1)<<endl;
}
void solve4(){
	sort(s+1,s+1+cnt);
	D[0]=1;
	for(int i=1;i<=m+1;i++) D[i]=((v*D[i-1]%MOD*(v-1)%MOD+D[i-1])%MOD)%MOD;
	int old=1,ans=1;
	for(int i=1;i<=cnt;i++){
		int ds=i;
		while(s[i+1]==s[i]+1) i++;
		ans=(ans*fast_pow(v*v%MOD,s[ds]-1-old+1)%MOD);
		//cout<<i<<" "<<ans<<endl;
		if(s[i]!=n)ans=(ans*D[i-ds]%MOD);
		else ans=(ans*D[i-ds]%MOD);
		old=s[i];
	}
	if(s[cnt]!=n)ans=(ans*fast_pow(v*v%MOD,n-s[cnt])%MOD);
	cout<<ans<<endl;
	num.clear();	
}
void solve(){
	cin>>n>>m>>v;
	bool f=0;
	cnt=0;
	bool A=1;
	memset(s,0,sizeof s);
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		if(a!=b) A=0;
		if(num[a]==0) num[a]=b,s[++cnt]=a;
		else if(num[a]!=b) f=1;
	}
	//cout<<n<<" "<<m<<" "<<v<<" "<<f<<endl;
	if(f==1){
		num.clear();
		cout<<0<<endl;
		return ;
	}
	if(n<=12) solve2();
	else if(A==1) solve1();
	else if(m==1) solve3();
	num.clear(); 
}
bool MB2;
void end(){
	cerr<<endl;
	cerr<<fixed<<setprecision(3)<<abs(&MB2-&MB1)/1024.0/1024.0<<"MB"<<endl;
	cerr<<fixed<<setprecision(3)<<(double)clock()/CLOCKS_PER_SEC<<"ms"<<endl;
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--) solve();
	//end();
}

