#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7,N=1000010;
long long a[N],ans=1,n,m,v,T,d=1,x,y;
void dfs(int p)
{
	if(p==n)
	{
		ans++;
		return;
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
		{
			if(a[p]==i)
			{
				if(a[p+1]==0)
				{
					a[p+1]=j;
					dfs(p+1);
					a[p+1]=0;
				}
				else if(a[p+1]!=j) continue;
				else dfs(p+1);
			}
			else dfs(p+1);
		}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--)
	{
		ans=1,d=0;
		cin>>n>>m>>v;
		memset(a,0,sizeof(a));
		for(int i=1;i<=m;i++)
		{
			cin>>x>>y;
			if(x<1000000&&y<1000000)
			{
				if(a[x]!=0&&a[x]!=y) d=1;
				a[x]=y;	
			}
		}
		if(d==1) 
		{
			cout<<0<<"\n";
			continue;
		}
		if(m==1)
		{
			for(int i=1;i<n;i++)
				ans=ans*v*v%M;
			cout<<ans<<"\n";
			continue;
		}
		if(n<=20)
		{
			dfs(1);
			cout<<ans-1<<"\n";
		}
		else
		{
			for(int i=1;i<n;i++)
				ans=ans*(v*(v-1)+1)%M;
			cout<<ans<<"\n";
			continue;
		}
	}
	
	return 0;
 } 
