#include<stdio.h>//35
#include<iostream>
#include<string>
#include<map>
using namespace std;
const int p=1000000007;
int T,n,m,v,c[100005],d[100005],val[100005],cnt;
long long ans;
bool flag1,flag2;
map<int,int> mod_usi;
int sto_explore_orz(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=1ll*ans*a%p;
		}
		a=1ll*a*a%p;
		b>>=1;
	}
	return ans;
}
int a[55],b[55],tmp[55];
bool check()
{
	for(int i=1;i<=n;i++)
	{
		tmp[i]=0;
	}
	for(int i=1;i<=m;i++)
	{
		tmp[c[i]]=d[i];
	}
	for(int i=1;i<n;i++)
	{
		if(tmp[i]==a[i]&&tmp[i+1]!=0&&tmp[i+1]!=b[i])return false;
	}
	return true;
}
void dfs(int i)
{
	if(i>=n)
	{
		ans+=check();
		return;
	}
	a[i]=1,b[i]=1;
	dfs(i+1);
	a[i]=1,b[i]=2;
	dfs(i+1);
	a[i]=2,b[i]=1;
	dfs(i+1);
	a[i]=1,b[i]=2;
	dfs(i+1);
	return;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		mod_usi.clear();
		flag1=true;
		flag2=false;
		cin>>n>>m>>v;
		if(n!=m)
		{
			flag1=false;
		}
		for(int i=1;i<=m;i++)
		{
			cin>>c[i]>>d[i];
			if(mod_usi.find(c[i])==mod_usi.end())
			{
				mod_usi[c[i]]=d[i];
			}
			else if(mod_usi[c[i]]!=d[i])
			{
				flag2=true;
			}
			if(c[i]!=i)
			{
				flag1=false;
			}
		}
		if(m==1)
		{
			cout<<sto_explore_orz(1ll*v*v%p,n-1)<<endl;
		}
		else if(flag1)
		{
			cout<<sto_explore_orz((1ll*v*(v-1)%p+1)%p,n-1)<<endl;
		}
		else if(flag2)
		{
			cout<<0<<endl;
		}
		else if(n<=12&&m<=12&&v<=2)
		{
			ans=0;
			dfs(1);
			cout<<ans<<endl;
		}
	}
	return 0;
}
