#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int T;
int n,m;
ll v;
ll ans;
ll a[15],p[15];
ll op[15][2];
unordered_map<ll,ll>pd;
struct node
{
	ll a,b;
}s[150000];
void dfs(int dep)
{
	if(dep>=n)
	{
		for(int i=1;i<=n;i++)p[i]=0;
		for(int i=1;i<n;i++)
		{
			if(!p[i])p[i]=a[i];
			if(p[i]==op[i][0])
			{
				if(op[i][1]!=a[i+1]&&a[i+1]!=0)return;
				p[i+1]=op[i][1];
			}
		}
		ans++;
		return;
	}
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			op[dep][0]=i;
			op[dep][1]=j;
			dfs(dep+1);
		}
	}
}
ll qpow(ll x,ll y)
{
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
//bool cmp(node i,node j){return i.a<j.a;}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		ans=0;
		bool bz=0;
		scanf("%d%d%lld",&n,&m,&v);
		if(n<=12)for(int i=1;i<=n;i++)a[i]=0;
		pd.clear();
		for(int i=1;i<=m;i++)
		{
			ll x,y;
			scanf("%lld%lld",&x,&y);
			s[i]={x,y};
			if(pd[x]&&pd[x]!=y)bz=1;
			pd[x]=y;
			if(n<=12)a[x]=y;
		}
		if(bz)
		{
			printf("0\n");
			continue;
		}
		if(m==n)
		{
			printf("%lld\n",qpow(v*(v-1)+1,n-1));
			continue;
		}
		else if(m==1)
		{
			ans=qpow(v,(s[1].a-1)*2)*qpow(v,(n-s[1].a)*2)%mod;
		}
		else dfs(1);
		printf("%lld\n",ans%mod);
	}
	return 0;
}
