#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int t;
const int MOD=1e9+7;
long long qpow(long long a,long long b){
	long long res=1;
	while(b){
		if(b&1) res=(a*res)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}
void solve(){
	int n,m,v;
	cin>>n>>m>>v;
	vector<int> vec;
	vec.resize(n+1,-1);
	unordered_set<int> st;
	unordered_map<int,unordered_set<int>> mp;
	int a,b;
	bool fail=0;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		if(vec[a]!=-1){
			fail=true;
			continue;
		}
		vec[a]=b;
		st.insert(b);
		mp[b].insert(a);
	}
	if(fail){
		cout<<"0\n";
		return;
	}
	long long ans=0;
	if(v>st.size())
	ans=(ans+(v-st.size())*v*(n-1)%MOD)%MOD;
	for(const auto&i:st){
		if(i>v) continue;
		unordered_set<int> st2;	
		//cout<<"check:"<<i<<'\n';
		if(mp.find(i)!=mp.end())
		for(const auto& st:mp[i]){
			if(st+1>n) continue;
			st2.insert(vec[st+1]);
			//cout<<vec[st+1]<<' ';
		}
		if(st2.size()==0||st2.size()==1&&st2.count(-1)) {
			ans=(ans+v)%MOD;
		}
		else if(st2.size()==1||(st2.size()==2&&st2.count(-1))) ans=(ans+1)%MOD;
	}
	cout<<ans<<'\n';
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
