#include<cstdio>
#include<algorithm>
#include<cstring>

namespace IO{
	constexpr int SIZE=1<<19;
	char iBuf[SIZE],*iS,*iT,ch;bool f;
	char oBuf[SIZE],*oS=oBuf,*oT=oBuf+SIZE;
	inline char gc(){return(iS==iT&&(iT=(iS=iBuf)+fread(iBuf,1,SIZE,stdin),iS==iT)?EOF:*iS++);}
	template<typename I>inline void read(I &x){
		for(f=0,ch=gc();ch<'0'||ch>'9';ch=gc())if(ch=='-')f=1;
		for(x=0;ch>='0'&&ch<='9';ch=gc())x=(x<<3)+(x<<1)+(ch&15);
		if(f)x=-x;return;
	}
	inline void flush(){fwrite(oBuf,1,oS-oBuf,stdout);oS=oBuf;return;}
	inline void putc(char x){*oS++=x;if(oS==oT)flush();return;}
	template<typename I>inline void write(I x){
		static char qu[55];char*tmp=qu;
		if(x<0)putc('-'),x=-x;
		do*tmp++=(x%10)^48;while(x/=10);
		while(tmp--!=qu)putc(*tmp);
		return;
	}
	struct flusher{~flusher(){flush();}}_;
}
using IO::read;using IO::write;using IO::gc;using IO::putc;

const int N=1e5+5,mod=1e9+7;

int qpow(int x,int y){
	int ans=1;
	while(y>0){
		if(y&1)ans=1ll*ans*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ans;
}

int T;
int n,m,v;
struct name{int c,d;}a[N];
bool cmp_name(name x,name y){return x.c<y.c;}

int Ans,cnt,ls;

int bz_sub1[N];
int dp[N][3];

bool pd_subA(){
	if(n!=m)return 0;
	for(int i=1;i<=m;i++)if(a[i].c!=i)return 0;
	return 1;
}

int main(){
	
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	
	read(T);
	while(T--){
		
		read(n);read(m);read(v);
		for(int i=1;i<=m;i++){
			read(a[i].c);read(a[i].d);
		}
		
		Ans=0;
		
		if(pd_subA()){
			Ans=(1ll*v*(v-1)%mod+1)%mod;
			Ans=qpow(Ans,n-1);
		}
		else if(m==1){
			Ans=1ll*v*v%mod;
			Ans=qpow(Ans,n-1);
		}
		else if(n<=12&&m<=12&&v<=2){
			for(int i=1;i<=n;i++)bz_sub1[i]=0;
			for(int i=1;i<=m;i++){
				if(bz_sub1[a[i].c]!=0&&bz_sub1[a[i].c]!=a[i].d)goto PRINT;
				bz_sub1[a[i].c]=a[i].d;
			}
			memset(dp,0,sizeof(dp));
			dp[1][bz_sub1[1]]=1;
			for(int i=1;i<n;i++)
			for(int col=0;col<3;col++){
				if(dp[i][col]==0)continue;
				if(col==0){
					(dp[i+1][bz_sub1[i+1]]+=1ll*dp[i][col]*4%mod)%=mod;
				}
				else{
					if(bz_sub1[i+1]==0){
						(dp[i+1][1]+=dp[i][col])%=mod;
						(dp[i+1][2]+=dp[i][col])%=mod;
						(dp[i+1][0]+=1ll*dp[i][col]*2%mod)%=mod;
					}
					else{
						(dp[i+1][bz_sub1[i+1]]+=1ll*dp[i][col]*2%mod)%=mod;
						(dp[i+1][bz_sub1[i+1]%2+1]+=dp[i][col])%=mod;
					}
				}
			}
			Ans=((dp[n][0]+dp[n][1])%mod+dp[n][2])%mod;
		}
		else{
			std::sort(a+1,a+m+1,cmp_name);
			
		}
		
		PRINT:;
		Ans=(Ans%mod+mod)%mod;
		write(Ans);putc('\n');
		
	}
	
	return 0;
}
