#include<bits/stdc++.h>
using namespace std;
#define p 1000000007
int t,n,m,v,c,d,a[100001],b[100001],ans;
bool flaga;
unordered_map<int,int>li;
long long qp(long long a,long long b)
{
	long long res=1;
	for(;b;b>>=1)
	{
		if(b&1)(res*=a)%=p;
		(a*=a)%=p;
	}
	return res;
}
void dfs(int st)
{
	if(st==n)
	{
		int ll[100];
		for(int i=1;i<=n;i++)ll[i]=li[i];
		for(int i=1;i<n;i++)
		{
			if(!ll[i]||ll[i]!=a[i])continue;
			if(ll[i+1]&&ll[i+1]!=b[i])goto nxt;
			ll[i+1]=b[i];
		}
		(++ans)%=p;
		nxt:return;
	}
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			if(li[st]==i&&li[st+1]&&li[st+1]!=j)continue;
			a[st]=i;
			b[st]=j;
			dfs(st+1);
		}
	}
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&t);
	while(t--)
	{
		flaga=1;
		ans=0;
		scanf("%d%d%d",&n,&m,&v);
		flaga&=n==m;
		li.clear();
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&c,&d);
			flaga&=c==i;
			if(li[c]&&li[c]!=d)
			{
				puts("0");
				goto nxt;
			}
			li[c]=d;
		}
		if(m==1)
		{
			printf("%lld\n",qp(1ll*v*v%p,n-1));
			continue;
		}
		if(flaga)
		{
			printf("%lld\n",qp((v*(v-1ll)+1)%p,n-1));
			continue;
		}
		dfs(1);
		printf("%d\n",ans);
		nxt:;
	}
	return 0;
}
