#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2*N,mod=1e9+7;
int t;
int n,m,v;
namespace task1
{
	int h[N],ne[M],e[M],idx=1;
	int x[N];
	bool flag;
	void add(int a,int b)
	{
		e[idx]=b,ne[idx]=h[a],h[a]=idx++;
	}
	struct node{
		int u,v;
	}edge[N];
	node op[4];
		int ans;
		bool vis[N];
	void dfs1(int u)
	{
//		cout<<ans<<' '<<u<<endl;
		if(u==n||u==2*n)
		{
			if(x[u])
			{
				if(u==n+(x[u]-1))flag=true;
			}
			else flag=true;
			return ;
		}
		for(int i=h[u];i;i=ne[i])
		{
			int v=e[i];
			if(vis[v])continue;
			vis[v]=true;
			dfs1(v);
		}
	}
	bool check()
	{

		for(int i=1;i<=n-1;i++)
		{
			if(x[i])
			{
				if(x[i]==edge[i].u)
				{
					
					add(i+(x[i]-1)*n,i+1+(edge[i].v-1)*n);
				}
				else
				{
					add(i+(x[i]-1)*n,i+1),add(i+(x[i]-1)*n,(i+1)+n);
				}
			}
			else
			{
				if(edge[i].u==1)
				{
					add(i,(i+1)+(edge[i].v-1)*n);
					add(i+n,(i+1));
					add(i+n,(i+1)+n);
				}
				if(edge[i].u==2)
				{
					add(i,i+1);
					add(i,(i+1)+n);
					add(i+n,(i+1)+(edge[i].v-1)*n);
				}
			}
		}
		flag=false;
		if(x[1])
		{
			memset(vis,0,sizeof vis);
			vis[1+(x[1]-1)*n]=true;
			dfs1(1+(x[1]-1)*n);
		}
		else
		{
			memset(vis,0,sizeof vis);
			vis[1]=true;
			dfs1(1);
			memset(vis,0,sizeof vis);
			vis[1+n]=true;
			dfs1(1+n);
		}
		return flag;
	}
	void dfs(int u)
	{
		if(u==n)
		{
			if(check())ans=(ans+1)%mod;
			return ;
		}
		for(int i=0;i<4;i++)
		{
			edge[u]=op[i];
			dfs(u+1);
		}
	}
	void work()
	{
		idx=1;
		memset(h,0,sizeof h);
		memset(x,0,sizeof x);
		memset(x,0,sizeof x);
		op[0]=(node){1,1},op[1]=(node){1,2},op[2]=(node){2,1},op[3]=(node){2,2};
		int cnt=0;
		ans=0;
		bool flag=0;
		for(int i=1;i<=m;i++)
		{
			int a,b;
			cin>>a>>b;
			if(x[a]!=0)
			{
				if(x[a]!=b)
				{
					flag=true;
				}
			}
			if(flag==true)continue;
			x[a]=b;
		}
		if(flag==true)
		{
			cout<<0<<endl;
			return ;
		}
		dfs(1);
		cout<<ans<<endl;
	}
}

int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>v;
		if(v<=2)task1::work();
	}
	return 0;
}

