#include<bits/stdc++.h>
using namespace std;
long long p=1e9+7;
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	long long T;
	cin>>T;
	while(T--){
		long long n,m,v;
		cin>>n>>m>>v;
		long long c[100005],d[100005];
		map<long long,long long> mp;
		map<long long,map<long long,long long> > vis;
		bool lp=false;
		bool llp=false;
		long long nv=0;
		for(long long i=1;i<=m;++i){
			cin>>c[i]>>d[i];
			if(c[i]!=i) lp=true;
			if(!mp[d[i]]){
				nv++;
			}
			mp[d[i]]++;
		}
		long long ans=0;
		if(!lp&&n==m){
			ans=(v-nv)*(v-nv)%p;
			for(long long i=1;i<n;++i){
				if(!vis[d[i]][d[i+1]]){
					vis[d[i]][d[i+1]]=1;
					ans++;
				}
			}
			if(mp[d[m]]==1) ans+=v-nv+2;
			if(mp[d[1]]==1) ans+=v-nv;
			ans%=p;
			cout<<ans<<"\n";
		}
	}
	return 0;
}
