#include<bits/stdc++.h>
using namespace std;
struct match{
	int c,d;
};
match a[100001];set<int>s;long long res=1;int b[100001];int itb;
bool find_in(int t){
    for(int i=0;i<itb;i++){
        if(b[i]==t)return true;
        if(b[i]>t)return false;
    }
    return false;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;cin>>T;
	while(T--){
		memset(a,0,sizeof a);s.clear();memset(b,0,sizeof b);itb=0;res=1;
		long long n,m,v;cin>>n>>m>>v;bool fl=0;bool fl2=1;
		for(int i=0;i<m;i++){
			cin>>a[i].c>>a[i].d;
			int tmp=s.size();s.insert(a[i].c);
			if(s.size()==tmp){//conflict detect
				fl2=0;
				for(int j=0;j<i;j++){
					if(a[j].c==a[i].c){
						if(a[j].d==a[i].d)break;
						else{
							fl=1;break;
						}
					}
				}
			}
			if(fl){
				cout<<0<<endl;
				break;
			}
		}if(fl)continue;
		if(m==n&&fl2){
			for(int i=1;i<n;i++){
				res*=(v-1)*v+1;res%=int(1e9+7);
			}
			cout<<res<<endl;continue;
		}
		for(auto it=s.begin();it!=s.end();it++){
            b[itb++]=*it;//cout<<b[itb-1]<<' ';
		}
		long long tmp1=((v-1)*v+1)%int(1e9+7);long long tmp2=v*v%int(1e9+7);
		for(int i=1;i<n;i++){
			if(find_in(i)&&find_in(i+1)){
				res*=tmp1;res%=int(1e9+7);
			}else{
				res*=tmp2;res%=int(1e9+7);
			}
		}
		cout<<res<<endl;
	}
	return 0;
}