#include<iostream>
#include<cstring>
#include<cstdio>
namespace io
{
	void read()
	{
		return;
	}
	template<typename nowtype,typename ...nexttype>
	void read(nowtype &now,nexttype &...next)
	{
		now=0;
		char c=getchar();
		int n(1);
#define isdigit(c) ((c)>='0'&&(c)<='9')
		while(!isdigit(c)){if(c=='-') n=-1;c=getchar();}
		while(isdigit(c)){now=(now<<1)+(now<<3)+(c^48);c=getchar();}
		now*=n;
#undef isdigit
		read(next...);
	}
}
using namespace io;
namespace SOLVE
{
	typedef long long ll;
	typedef unsigned long long ull;
	const int const1=2e6+10;
	const int mod=1e9+7;
	int n,m,x[const1],ans;
	bool check(int a,int b)
	{
		if(a==b)
		{
			for(int i=1;i<=n;++i)
			{
				if(x[i]==a)
				{
					a=-1;
					continue;
				}
				if(a==-1&&x[i]!=b&&x[i]!=0) return false;
			}
		}
		else
		{
			for(int i=1;i<=n;++i) if(x[i]==a&&(x[i+1]!=b&&x[i+1]!=0)) return false;
		}
		return true;
	}
	ll pow(ll x,ll p)
	{
		ll ans(1);
		while(p)
		{
			if(p&1) ans=(ans*x)%mod;
			p>>=1;
			x=x*x%mod;
		}
		return ans%mod;
	}
	void solve()
	{
		int i,j,v,c,d;
		std::memset(x,0,sizeof x);
		ans=0;
		read(n,m,v);
		if(m==1)
		{
			read(c,d);
			printf("%lld\n",1ll*pow(1ll*v,2*(n-1)%mod));
			return;
		}
		for(i=1;i<=m;++i)
		{
			read(c,d);
			if(!x[c]) x[c]=d;
			else
			{
				printf("0\n");
				return;
			}
		}
		if(v<=2)
		{
			for(i=1;i<=v;++i) for(j=1;j<=v;++j) if(check(i,j)) ++ans;
			printf("%d\n",ans);
		}
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	read(t);
	while(t--) SOLVE::solve();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
