#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
const ll mod=1e9+7;
ll T,n,m,v,ans,tot;
ll g[N][3];
bool flag,kkk,ttt;
map<ll,ll> cnt;
void dfs(ll p,ll num){
	if(p==n){
		ans=(ans+1)%mod;
		return;
	}
	for(int i=1;i<=v;i++){
		if(i==num){
			if(!cnt.count(p+1)){
				for(int j=1;j<=v;j++)
					dfs(p+1,j);
			}
			else dfs(p+1,cnt[p+1]);
			continue;
		}
		for(int k=1;k<=v;k++){
			if(k>1&&cnt.count(p)!=0) break;
			if(!cnt.count(p+1)){
				for(int j=1;j<=v;j++)
					dfs(p+1,j);
			}
			else dfs(p+1,cnt[p+1]);
		}
	}
}
ll quick_pow(){
	int sum=1,res=(v*(v-1));
	int b=n-1;
	while(b){
		if(b&1) sum=(sum*res)%mod;
		res=(res*res)%mod;
		b>>=1;
	}
	return sum;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		flag=true;kkk=true;ttt=true;
		cnt.clear();tot=0;
		if(n!=m) flag=false;
		for(ll i=1,c,d;i<=m;i++){
			cin>>c>>d;
			if(cnt.count(c)!=0){
				ttt=false;
				break;
			}
			if(m==n&&c!=i) flag=false;
			if(d!=1) kkk=false;
			cnt[c]=d;
		}
		if(ttt==false){
			cout<<0<<endl;
			continue;
		}
		ans=0;
		if(flag==true){
			cout<<quick_pow()+1<<endl;
			continue;
		}
		if(!cnt.count(1)){
			for(int i=1;i<=v;i++)
				dfs(1,i);
		} 
		else dfs(1,cnt[1]);
		cout<<ans<<endl;
	}
	return 0;
} 
