#include <iostream>
#include <stdio.h>
#define MAXNUM 100005
using namespace std;

int T,ans=0;
int n,m,v;
int x[MAXNUM*10];
int a[MAXNUM*10],b[MAXNUM*10];
int c[MAXNUM],d[MAXNUM];
 
bool check()
{
	for(int i=1;i<n;i++)
	{
		if(x[i]==a[i])
		{
			if((x[i+1]!=0)&&(x[i+1]!=b[i])) return false;
		}
	}
	return true;
}

void solve(int nowStep)
{
	if(nowStep==n)
	{
		if(check()) ans++,ans=ans%1000000007;
		return;
	}
	for(int i=1;i<=v;i++)
	{
		a[nowStep]=i;
		for(int j=1;j<=v;j++)
		{
			b[nowStep]=j;
			solve(nowStep+1);
		}
	}
}

int main()
{
	FILE *fp=fopen("assign.in","r");
	FILE *fl=fopen("assign.out","w");
	fscanf(fp,"%d",&T);
	for(int k=0;k<T;k++)
	{
		ans=0;
		fscanf(fp,"%d%d%d",&n,&m,&v);
		bool tmp=true; 
		for(int i=0;i<m;i++)
		{
			fscanf(fp,"%d%d",&c[i],&d[i]);
			if(x[c[i]]!=0)
			{
				if(d[i]!=x[c[i]]) 
				{
					fprintf(fl,"0\n");
					//cout<<0<<endl;
					tmp=false;
					break;
				}
			}
			x[c[i]]=d[i];
		}
		if(!tmp) continue;
		solve(1);
		fprintf(fl,"%d\n",ans);
		//cout<<ans<<endl;
	}
	fclose(fp);
	fclose(fl);
	
	return 0;
}
