#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,k) for(register ll i=j;i<=k;++i)
using namespace std;
const ll N=1e6+5,mod=1e9+7;
ll n,m,T,v,c[N],d[N],a[N],t[N],ans,bz1,bz,mx,mn,tot,x,y;
map<ll,ll>mp;
map<ll,ll>mp1;
struct edge{
	ll c,d;
}l[N];
bool cmp(ll a,ll b){
	return a<b;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		bz1=bz=tot=0;
		ans=1;
		cin>>n>>m>>v;
		if(m==n){
			mp1[n]=0;
			fo(i,1,m){
				cin>>c[i]>>d[i];
				if(a[d[i-1]]==0)a[d[i-1]]=d[i],tot++;
				else if(a[d[i-1]]!=d[i])bz=1;
			}
			if(bz==1){
				cout<<"0"<<endl;
				continue;
			}
			fo(i,tot,v){
				ans=(ans*i)%mod;
			}
			cout<<ans<<endl;
			continue;
		}
		fo(i,1,m){
			cin>>c[i]>>d[i];
			if(mp[c[i]]==0||mp[c[i]]==d[i])mp[c[i]]=d[i];
			else bz=1;
		}
		fo(i,1,m){
			mp[c[i]]=0;
		}
	}
	return 0;
}
