#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e5+5,mod=1e9+7;
int t,n,m,v,c[M],d[M],a[M],xl[M][5];
int qpow(int a,int b,int p)
{
	int s=1;
	while(b)
	{
		if(b&1) s=s*a%p;
		b>>=1;
		a=a*a%mod;
	}
	return s;
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&t);
	while(t--)
	{
		bool ts=0;
		memset(a,0,sizeof(a));
		scanf("%lld%lld%lld",&n,&m,&v);
		for(int i=1;i<=m;i++)
		{
			scanf("%lld%lld",&c[i],&d[i]);
			if(c[i]!=i) ts=1;
		}
		if(n<=9)
		{
			int cs=pow(4,n-1)-1,ans=0;
			for(int i=0;i<=cs;i++)
			{
				int er[15],c1=0,t=i,pd=0;
				memset(er,0,sizeof(er));
				memset(a,0,sizeof(a));
				for(int j=1;j<=m;j++)
				{
					if(!a[c[j]]) a[c[j]]=d[j];
					else
					{
						if(a[c[j]]!=d[j])
						{
							pd=1;
							break;
						}
					}
				}
				if(pd) continue;
				while(t!=0)
				{
					er[++c1]=t%4;
					t/=4;
				}
				for(int j=1;j<n;j++)
				{
					if(er[j]==0) xl[j][0]=1,xl[j][1]=1;
					if(er[j]==1) xl[j][0]=1,xl[j][1]=2;
					if(er[j]==2) xl[j][0]=2,xl[j][1]=1;
					if(er[j]==3) xl[j][0]=2,xl[j][1]=2;
				}
				for(int j=1;j<n;j++)
				{
					if(a[j]==xl[j][0])
					{
						if(!a[j+1]) a[j+1]=xl[j][1];
						else
						{
							if(a[j+1]!=xl[j][1])
							{
								pd=1;
								break;
							}
						}
					}
				}
				if(!pd) ans++;
			}
			printf("%lld\n",ans);
			continue;
		}
		if(m==n&&!ts) printf("%lld\n",qpow((v*v%mod-v+1+mod)%mod,n-1,mod));
		else printf("0\n");
	}
	return 0;
}
