#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=101010;
ll T,n,m,v,ans,mod=1e9+7,l,p,q,b[5010][20],a[20],ans1,k,sum;
struct tt{
	ll x,y;
}s[N];
struct node{
	ll xx,yy; 
}c[20];
void dfs(int x,int y){
	if(x>=n-k){
		ans++;
		for(int i=1;i<=n;i++)b[ans][i]=a[i];
		return;
	}
	if(a[y]==0){
		for(int j=1;j<=v;j++){
			a[y]=j;
			dfs(x+1,y+1);
			a[y]=0;
		}
	}
	else dfs(x,y+1);
}
void dfs1(int x){
	if(x>=n-1){
		for(int i=1;i<=ans;i++){
			p=0;
			for(int j=1;j<n;j++){
				if(b[i][j]==c[j].xx&&c[j].yy!=b[i][j+1]){
					p=1;
					break;
				}
			}
			if(p==0){
				ans1++;
				return;
			}
		}
		return ;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			c[x+1].xx=i,c[x+1].yy=j;
			dfs1(x+1);
			c[x+1].xx=c[x+1].yy=0;
		}
		
	}
}
ll qpow(ll x,ll y){
	ll sum=1;
	while(y!=0){
		if(y&1)sum=sum*x%mod;
		x*=x,x%=mod;
		y>>=1;
	}
	return sum%mod;
}
bool cmp(tt a,tt b){
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		p=q=k=ans=ans1=sum=0;
		scanf("%lld%lld%lld",&n,&m,&v);
		for(int i=1;i<=m;i++){
			scanf("%lld%lld",&s[i].x,&s[i].y);
			if(s[i].x<=20){
				if(a[s[i].x]==0)k++;
				a[s[i].x]=s[i].y;
			}
		}
		sort(s+1,s+m+1,cmp);
		for(int i=1;i<=m;i++){
			if(s[i].x==s[i-1].x&&s[i].y!=s[i-1].y)q=1;
			if(s[i].x!=s[i-1].x+1)p=1;
			if(s[i].x!=s[i-1].x)sum++;
		}
		if(q==1){
			printf("0\n");
			continue;
		}
		if(n<=12&&m<=12&&sum>1){
			dfs(0,1);
			dfs1(0);
			printf("%lld\n",ans1);
		}
		else{
			l=s[1].x;
			if(l>1)ans=qpow(v*v%mod,l-1)%mod;
			else ans=1;
			for(int i=2;i<=m;i++){
				if(s[i].x==s[i-1].x)continue;
				if(s[i].x==l+1)ans=ans*(v*(v-1)%mod+1)%mod; 
				else ans=ans*qpow(v*v%mod,s[i].x-l)%mod; 
				l=s[i].x;
			}
			printf("%lld\n",ans*qpow(v*v%mod,n-l)%mod);
		}
	}
	return 0;
}
