#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long mod=1e9+7;
const long long N=200009;
long long ansn,n,m,v,aa[N],b[N],c[N],d[N];
long long power(long long a,long long b)
{
	long long ans=1,base=a;
	while(b)
	{
		if(b&1) ans=ans*base%mod;
		base=base*base%mod,b>>=1;
	}
	return ans%mod;
}
void dg(int x)
{
	if(x>2*(n-1))
	{
		for(int i=1;i<=n;i++)
			d[i]=c[i];
		for(int i=1;i<n;i++)
			if(d[i]!=0&&d[i]==aa[i])
			{
				if(d[i+1]!=0&&d[i+1]!=b[i])
					return ;
				d[i+1]=b[i];
			}
		ansn++;
		return ;
	}
	if(x>n-1)
	{
		for(int i=1;i<=v;i++)
		{
			b[x-(n-1)]=i;
			dg(x+1);
			b[x-(n-1)]=0;
		}
	}
	else
	{
		for(int i=1;i<=v;i++)
		{
			aa[x]=i;
			dg(x+1);
			aa[x]=0;
		}
	}
}
struct node{
	long long c,d;
}a[N];
bool cmp(node x,node y)
{
	return x.c<y.c;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	long long T;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld%lld",&n,&m,&v);
		for(long long i=1;i<=m;i++)
			scanf("%lld%lld",&a[i].c,&a[i].d);
		if(n<=12)
		{
			for(long long i=1;i<=n;i++)
				c[i]=0;
			bool flag=0;
			for(long long i=1;i<=m;i++)
			{
				if(c[a[i].c]!=0&&c[a[i].c]!=a[i].d) {flag=1;break;}
				c[a[i].c]=a[i].d;
			}
			if(flag==1) printf("0\n");
			else ansn=0,dg(1),printf("%lld\n",ansn);
		}
		else
		{
			sort(a+1,a+m+1,cmp);
			long long ans=power(v,2*(n-1)),sum=0;
			for(long long i=1;i<m;i++)
			{
				if(a[i].c!=a[i+1].c)
				{
					long long cha=a[i+1].c-a[i].c;
					long long hou=power(v,2*(n-a[i+1].c));
					long long qian=(power(v,2*(a[i].c-1))-sum+mod)%mod;
					long long jian=power(v,cha-1)*(v-1)%mod;
					ans=(ans-(jian*hou%mod*qian%mod)+mod)%mod;
					sum=(sum*power(v,2*cha)+jian*qian%mod)%mod;
				}
				else if(a[i].c==a[i+1].c&&a[i].d!=a[i+1].d) {ans=0;break;}
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

