#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long ttt,n,m,v,c[100005],d[100005],jie[100005],jie1[100005],ans,a[100005],b[100005],val[100005],zzz[100005];
map<long long ,long long>s;
long long qpow(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
void dfs(long long o)
{
	if(o>=n)
	{
		for(int i=1;i<=n;i++) zzz[i]=val[i];
		for(int i=1;i<n;i++)
		{
			if(val[i]==a[i])
			{
				if(val[i+1]!=b[i]&&val[i+1]!=-1)
				{
					for(int i=1;i<=n;i++) val[i]=zzz[i];
					return ;
				}
				val[i+1]=b[i];
			} 
		}
		for(int i=1;i<=n;i++) val[i]=zzz[i];
		(ans+=1)%=mod;
		return ;
	}
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			a[o]=i;b[o]=j;
			dfs(o+1);
		}
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&ttt);
	while(ttt--)
	{
		ans=0;
		scanf("%lld%lld%lld",&n,&m,&v);
		s.clear();
		bool bz=1,kkk=0;
		for(int i=1;i<=m;i++)
		{
			scanf("%lld%lld",&c[i],&d[i]);
			if(s[c[i]]!=0&&s[c[i]]!=d[i]) kkk=1;
			s[c[i]]=d[i];
			if(c[i]!=i) bz=0;
		}
		if(kkk){printf("0\n");continue;}
		if(m==1)
		{
			printf("%lld\n",qpow(v*v%mod,n-1)%mod);continue;
		}
		if(m==n&&bz)
		{
			jie[0]=1;
			for(int i=1;i<=n;i++) jie[i]=jie[i-1]*i%mod;
			jie1[n]=qpow(jie[n],mod-2);
			for(int i=n-1;i>=0;i--) jie1[i]=jie1[i+1]*(i+1)%mod;
			long long sum=0;
			for(int i=0;i<n;i++)
			{
				(sum+=jie[n-1]*jie1[n-1-i]%mod*jie1[i]%mod*qpow((v-1)*v%mod,n-i-1)%mod)%=mod;
			}
			printf("%lld\n",sum);continue;
		}
		for(int i=1;i<=n;i++) val[i]=-1;
		for(int i=1;i<=m;i++) val[c[i]]=d[i];
		dfs(1);
		printf("%lld\n",ans);
	}
	return 0;
}
