考场上正解3h没调出来，自闭了

#define allLL
#include<bits/stdc++.h>
#define LL long long
#ifdef allLL
#define int LL
const int INF=(1e18);
#else
const int INF=1e9+9;
#endif
#define N 500005
#define P 1000000007
template<typename T>T Max(T x,T y){return (x<y?y:x);}
template<typename T>T Min(T x,T y){return (x<y?x:y);}
template<typename T>void read(T&x){
x=0;char c=getchar();/*T fh=1;*/while(c<'0'||'9'<c){/*if(c=='-')fh=-1;*/c=getchar();}
while('/'<c&&c<':'){x=x*10+(c^'0');c=getchar();}/*x*=fh;*/}
template<typename T>void write(T x){
if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar('0'+x%10);}
using namespace std;
int n,m,v;
pair<int,int> p[N];
struct matx{
	int mp[3][3];
	int n,m;
	int* operator [](int id){return mp[id];}
	matx operator * (matx oth){
		matx c={{},n,oth.m};
//		cout<<n<<','<<m<<","<<oth.m<<"::::::::::::::::::\n";
		for(int i=1;i<=n;i++){
			for(int j=1;j<=oth.m;j++){
				c[i][j]=0;
				for(int k=1;k<=m;k++){
//					cout<<":::::::::::::"<<mp[i][k]<<"*"<<oth[k][j]<<":\n";
					c[i][j]=(c[i][j]+mp[i][k]*oth[k][j])%P;
				}
			}
		}
		return c;
	}
};
const matx ii={{{},{0,1,0},{0,0,1}},2,2};
matx qp(matx a,int b){
	if(b==0)return ii;
	if(b==1)return a;
	matx c=qp(a,b>>1);
	if(b&1)return c*c*a;
	else return c*c;
}
#undef int
int main(){
#ifdef allLL
#define int LL
#endif
	int T;
	read(T);
	while(T--){
		read(n);
		read(m);
		read(v);
		for(int i=1;i<=m;i++){
			read(p[i].first);
			read(p[i].second);
		}
		sort(p+1,p+m+1);
		int fl=0;
		for(int i=1;i<m;i++){
			if(p[i].first==p[i+1].first&&p[i].second!=p[i+1].second){
				fl=1;
				break;
			}
		}
		if(fl){
			puts("0");
			continue;
		}
//		if(n<=12){
//			bl::solve();
//			continue;
//		}
		m=unique(p+1,p+m+1)-p-1;
//		cout<<m<<"::::\n"; 
		matx u={{},1,2};
		matx m1={{},2,2};
		matx m2={{},2,2};
		matx m3={{},2,2};
		
		m1[1][1]=v*v%P;m1[1][2]=0;
		m1[2][1]=(v-1)*v%P;m1[2][2]=v;
		
		
		m2[1][1]=0;m2[1][2]=v*v%P;
//		cout<<m2.m<<"::\n";
		m2[2][1]=0;m2[2][2]=(v+(v-1)*(v-1))%P;
		
		m3[1][1]=0;m3[1][2]=0;
//		cout<<m2.m<<"::\n";
		m3[2][1]=0;m3[2][2]=(v*v-(v-1))%P;
		if(p[1].first==1){
			if(m>1&&p[2].first==2){
				u[1][1]=0,u[1][2]=(v*v-(v-1))%P;
//			cout<<u[1][1]<<','<<u[1][2]<<":::\n";
				for(int i=3;i<=m;i++){
					if(p[i].first==p[i-1].first+1)u=u*m3;
					else{
						if(p[i].first-p[i-1].first-1>0)u=u*qp(m1,p[i].first-p[i-1].first-1);
						u=u*m2;
					}
		//			puts("*");
//					cout<<u[1][1]<<','<<u[1][2]<<":::\n";
				}
				if(p[m].first!=n){
					u=u*qp(m1,n-p[m].first);
		//			cout<<u[1][1]<<','<<u[1][2]<<":::\n";
				}
			}
			else{
				if(n==1)u[1][1]=0,u[1][2]=1;
				else{
					u[1][1]=v*v-v,u[1][2]=v%P;
//					cout<<u[1][1]<<','<<u[1][2]<<":::\n";
					for(int i=2;i<=m;i++){
						if(p[i].first==p[i-1].first+1)u=u*m3;
						else{
							if(p[i].first-p[i-1].first-1-(i==2)>0)u=u*qp(m1,p[i].first-p[i-1].first-1);
							u=u*m2;
						}
			//			puts("*");
//						cout<<u[1][1]<<','<<u[1][2]<<":::\n";
					}
				}
				if(p[m].first!=n){
					if(n>2)u=u*qp(m1,n-p[m].first-1);
//					cout<<u[1][1]<<','<<u[1][2]<<":::\n";
				}
			}
		}
		else{
			u[1][1]=1,u[1][2]=0;
			
//			cout<<u[1][1]<<','<<u[1][2]<<":::\n";
			for(int i=1;i<=m;i++){
				if(p[i].first==p[i-1].first+1)u=u*m3;
				else {
					if(p[i].first-p[i-1].first-1-(i==1)>0)u=u*qp(m1,p[i].first-p[i-1].first-1);
					u=u*m2;
				}
	//			puts("*");
//				cout<<u[1][1]<<','<<u[1][2]<<":::\n";
			}
			if(p[m].first!=n){
				u=u*qp(m1,n-p[m].first);
	//			cout<<u[1][1]<<','<<u[1][2]<<":::\n";
			}
		}
//		cerr<<":::::";
//		cout<<"*";
		write((u[1][1]+u[1][2])%P);
		puts("");
	}
	return 0;
#undef int
}
/*
10
5 1 2
1 2
*/
/*
1
10 5 2
2 2
3 2
4 2
7 2
10 2

1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2
*/
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

*/