#include<bits/stdc++.h> 
using namespace std;
#define ll long long
const int N=1e6+10,R=1e9+7;
ll T,n,m,v;
ll a[N],b[N][2],ans;ll fd[N];
ll ksm(ll a,ll x)
{
	ll s=a,sum=1;
	while(x)
	{
		if(x&1) sum=sum*s%R;
		s=s*s%R;
		x>>=1; 
	 }
	return sum;
}
bool chk()
{
	for(ll i=1;i<n;i++)
	{
		if(a[i])
		{
			if(a[i]==b[i][0])
			{
				if(a[i+1]&&a[i+1]!=b[i][1])
				  return false;
			}
		}
	}
	return true;
}
void dfs(ll p)
{
	if(p==n)
	{
		if(chk())
		{
			ans++;
			
		}
		return;
	}
	
	for(ll i=1;i<=v;i++)
	{
		for(ll j=1;j<=v;j++)
		{
			b[p][0]=i;
			b[p][1]=j;
			dfs(p+1);
		}
	}
}
int main()
{
	
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		bool f=true,fa=true;
		ans=0;
		memset(a,0,sizeof(a));
		scanf("%lld%lld%lld",&n,&m,&v);
		for(ll i=1,c,d;i<=m;i++)
		{
			scanf("%lld%lld",&c,&d);
			if(a[c]&&a[c]!=d)
			{
			    f=false;
			}
			else
			{
				a[c]=d;
			}
		}
		if(!f) 
		{
			printf("0\n");
			continue;
		}
		if(m==1)
		{
			ans=((ll)v*v)%R;
			ans=ksm(ans,n-1);
			printf("%lld\n",ans%R);
			continue;
		}
		for(ll i=1;i<=n;i++)
		  if(!a[i])
		  {
		  	fa=false;
		  	break;
		  }
		if(fa)
		{
			ans=(ll)(1+(v-1)*v)%R;
			ans=ksm(ans,n-1);
			printf("%lld\n",ans%R);
			continue;
		}
		if(n<=12&&m<=12&&v<=2)
		{
			dfs(1);	
			printf("%lld\n",ans%R);
			continue;	
		}		
		ans=1;
		memset(fd,0,sizeof(fd));
		for(ll i=1;i<n;i++)
		{
			if(fd[i])
			{
				if(a[i+1])
				{
					ans=ans*(1+(v-1)*v)%R;
					fd[i+1]=1;
				 }
				else
				{
					ans=ans*v*v%R;
					fd[i+1]=1;
				}
			}
			else if(a[i])
			{
				ans=ans*v*v%R;
				fd[i+1]=1;
			}
			else
			{
				ans=ans*v*v%R;
			}
		}
		printf("%lld\n",ans%R);
	}
	
	return 0;
}
