#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=1e9+7,N=1e5+10;
int n,m,T,v,a[N],b[N],c[N],d[N];
ll ans=0;
ll quick(int x,int y)
{
	ll k=1;
	if(y==0) return 1;
	if(y%2==1) k*=x;
	ll res=quick(x,y/2);
	k=(ll)(res*res%P)*k%P;
	//cout<<y<<" "<<k<<endl;
	return k;
}
bool check(int x)
{
	if(x==n+1)
	{
		for(int i=1;i<n;i++)
		{
			if(d[i]==a[i])
			{
				if(b[i]!=d[i+1]) return false;
			}
		}
		return true;
	}
	if(c[x]!=0)
	{
		d[x]=c[x];
		return check(x+1);
	}
	for(int i=1;i<=v;i++)
	{
		d[x]=i;
		if(check(x+1)) return true;
	}
	return false;
}
void dfs(int x)
{
	if(x==n+1)
	{
		memset(d,0,sizeof(d));
		if(check(1)) ans=(ans+1)%P;
		return;
	}
	for(int i=1;i<=v;i++)
	{
		a[x]=i;
		for(int j=1;j<=v;j++)
		{
			b[x]=i;
			dfs(x+1);
		}
	}
}
int main()
{
	int i,j,k,l,x,y;
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		memset(c,0,sizeof(c));
		scanf("%d%d%d",&n,&m,&v);
		int flag=0;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			if(n>=12) continue;
			if(c[x]==0||c[x]==y) c[x]=y;
			else flag=1;
		}
		if(flag==1)
		{
			printf("0\n");
			continue;
		}
		if(m==1) printf("%lld\n",quick(v,2*n-2));
		else if(n<=12) dfs(1);
	}
}
