#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e5;
int t,n,v,m,num[N],a[N],b[N],x[N],ans;
int c,d;
int pow1(long long x,int k)
{
//	cout<<1;
	long long ans=1;
	long long base=x;
	while(k)
	{
//		cout<<k;
		if(k%2==1)
		{
			ans=(ans*base)%mod;
		} 
		base=(base*base)%mod;
		k/=2;
	}
	return ans;
}
bool check(int dep)
{
//	cout<<dep<<" ";
	if(dep==n+1) return 1;
	for(int i=1;i<=v;i++)
	{
		if(dep>1&&((x[dep-1]==a[dep-1]&&i!=b[dep-1])||(num[dep]>0&&i!=num[dep]))) continue;
		x[dep]=i;
		if(check(dep+1)) return 1;
	}
	return 0;
}
void dfs(int dep)
{
	if(dep==n)
	{
//		for(int i=1;i<=n;i++)
//		{
//			cout<<a[i]<<" ";
//		}
//		puts("");
//		for(int i=1;i<=n;i++)
//		{
//			cout<<b[i]<<" ";
//		}
//		puts("");
		if(check(1))
		{
			ans++;
		}
		return ;
	}
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			a[dep]=i;
			b[dep]=j;
			dfs(dep+1);
		}
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--)
	{
		memset(num,0,sizeof(num));
		cin>>n>>m>>v;
		ans=0;
		if(m==1)
		{
			cin>>c>>d;
			cout<<pow1((1ll*v*v)%mod,n-1)%mod<<endl;
			continue;
		}
		if(v<=2&&n<=12)
		{
			bool flag=0;
			for(int i=1;i<=m;i++)
			{
				cin>>c>>d;
				if(num[c]!=d&&num[c]>0)
				{
					flag=1;
					break;
				}
				num[c]=d;
			}
			if(flag){
				puts("0");
				continue;
			}
			dfs(1);
			cout<<ans<<endl;
			continue;
		}
		for(int i=1;i<=m;i++)
		{
			cin>>c>>d;
			num[c]=d;
		}
		cout<<pow1((1ll*v*(v-1)+1)%mod,n-1)%mod<<endl;
	}
	return 0;
}

