#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const long long mod=1e9+7;
int t,n,m,a[N],b[N],c[N],d[N],p[N],cnt1,cnt2;
long long v,ans;
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int dfs(int x,int s,int t,bool z)
{
	if(x+1==n) return 1;
	a[x]=((1<<(x-1))&1)+1,b[x]=((1<<(x-1))&1)+1;
	if(d[x])
	{
		if(z&&d[x]!=b[x-1]) return 0;
		else
		{
			if(d[x]==a[x]) return dfs(x+1,s,t,1);
			else return dfs(x+1,s,t,0);
		}
	}
	else return dfs(x+1,s,t,1)||dfs(x+1,s,t,0);
}
long long q_pow(long long x,long long k)
{
	long long ans=1;
	while(k)
	{
		if(k&1) ans=ans*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return ans;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	srand(time(0));
	t=read();
	while(t--)
	{
		n=read(),m=read();
		cin>>v;
		memset(d,0,sizeof(d));
		for(int i=1;i<=m;i++) c[i]=read(),d[c[i]]=read(); 
		if(v<=2)
		{
			for(int s=0;s<(1<<(n-1));s++)
			{
				for(int t=0;t<(1<<(n-1));t++)
				{
					ans+=dfs(1,s,t,1)+dfs(1,s,t,0);
					ans%=mod;
				}
			}
			cout<<ans<<endl;
			continue;
		}
		if(n==m)
		{
			cout<<((v-1)*v+1)%mod*(n-1)%mod<<endl;
			continue;
		}
		cout<<rand()%mod<<endl;
	}
	return 0;
}
