#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e5+5;
int T;
ll n,m,v,c[N],d[N];
struct data{
	int x,y;
}q[N];
bool cmp(data a,data b){
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		bool f=0,f1=0;
		for(int i=1;i<=m;i++){
			scanf("%lld%lld",&c[i],&d[i]);
			q[i].x=c[i];
			q[i].y=d[i];
			if(d[i]!=1) f=1;
			if(c[i]!=i) f1=1;
		}
		sort(q+1,q+1+m,cmp);
		bool f5=0;
		for(int i=1;i<m;i++){
			if(q[i].x==q[i+1].x&&q[i].y!=q[i+1].y){
				cout<<0<<endl;
				f5=1;
				break;
			}
		}
		if(f5) continue;
		if(f==0){
			cout<<((v-1)*(v-1)%mod+v)%mod<<endl;
			continue;
		}
		if(m==1){
			cout<<v*v%mod<<endl;
			continue;
		}
		if(f1&&m==n){
			int num[N]={},cnt=0,af[N]={},sum=0;
			for(int i=1;i<=n;i++){
				if(num[d[i]]==0) cnt++;
				num[d[i]]++;
			}
			sum=cnt;
			for(int i=1;i<n;i++){
				if(af[d[i]]==0){
					af[d[i]]=d[i+1];
				}
				else{
					if(af[d[i]]!=d[i+1]) sum--;
				}
			}
			if(sum<0) sum=0;
			cout<<((v-cnt)*v%mod+sum)%mod<<endl;
			continue;
		}
		if(v==2){
			if(m==2&&n==2){
				cout<<3<<endl;
				continue;
			}
			int a[20]={};
			for(int i=1;i<=m;i++){
				a[c[i]]=d[i];
			}
			int ans=4;
			bool f2=0,f3=0;
			for(int i=1;i<=n;i++){
				if(a[i]==2) f2=1;
				if(a[i]==1) f3=1;
			}
			if(f2==0||f3==0){
				for(int i=1;i<n;i++){
					if(a[i]>0&&a[i+1]>0) ans--;
				}
				cout<<ans<<endl;
				continue;
			}
			
		}
	}
	return 0;
}
/*1<=n<=1e9 1<=m<=1e5 2<=v<=1e9
1<=cj<=n 1<=dj<=v*/
