#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll Mod=1e9+7;

int T;ll ans;
int n,m,v;
int num[1000001];
int t[1000001];

struct node
{
	int a;
	int b;
};
node opt[1000001];


bool check()
{
	for(int i=1;i<=n;i++) t[i]=num[i];
	for(int i=1;i<=n-1;i++)
	{
		if(t[i]==opt[i].a)
		{
			if(t[i+1]!=opt[i].b&&t[i+1]!=-1) return 0;
			else t[i+1]=opt[i].b;
		}
	}
	return 1;
}

void dfs(int addr)
{
	if(addr>n-1)
	{
		if(check()) ans++;
		return ;
	}
	
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
		{
			opt[addr].a=i;opt[addr].b=j;
			dfs(addr+1);
			opt[addr].a=0;opt[addr].b=0;
		}
	}
}

int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	
	scanf("%d",&T);
	while(T--)
	{
		for(int i=1;i<=1000000;i++) num[i]=-1;
		ans=0;
		bool flag=0;
		
		scanf("%d%d%d",&n,&m,&v);
		for(int i=1;i<=m;i++)
		{
			int c,d;
			scanf("%d%d",&c,&d);
			if(num[c]!=-1&&d!=num[c]) flag=1;
			else num[c]=d;
		}
		if(flag) printf("0\n");
		else 
		{
			dfs(1);
			printf("%lld\n",ans%Mod);
		}
	}
	
	return 0;
}
