#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int N = 100;
int c[N],d[N],ar[N],car[N];
int n,m,v,ans;
void copyy()
{
	for(int i = 1; i <= 99; i++)car[i] = ar[i];
}
void tAk()
{
	ans = 1;
	int tmp = (v-1)*v;
	tmp++;
	tmp%=MOD;
	for(int i = 1; i <= n-1; i++)
	{
		ans*=tmp;
		ans%=MOD;
	}
	cout << ans << '\n';
	return;
}
int check(string s)
{
//	cout << s << '\n';
	copyy();
	int aa,bb;
	for(int i = 1; i < n; i++)
	{
		aa = s[i*2-1]-'0';
		bb = s[i*2]-'0';
//		cout << aa << ' ' << bb << '\n';
		if(car[i]==aa&&car[i+1]!=bb&&car[i+1]!=-1)return 0;
		else if(car[i]==aa)car[i+1]=bb;
	}
	return 1;
}
void dfs(int step, string s)
{
	if(step==(n-1)*2)
	{
		ans+=check(s);
		return;
	}
	step++;
	dfs(step,s+'1');
	dfs(step,s+'2');
	return;
}
void tNk()
{
	ans=0;
	dfs(0," ");
	cout << ans%MOD << '\n';
}
void solve()
{
	bool imflag = 0;
	int aaa,bbb;
	ans = 0;
	cin >> n >> m >> v;
	if(n>14)imflag = 1;
	for(int i = 1; i <= 14; i++)ar[i]=-1;
	for(int i = 1 ; i <= m; i++)
	{
		if(imflag)
		{
			cin >> aaa >> bbb;
			continue;
		}
		cin >> c[i] >> d[i];
		
		if(ar[c[i]]!=-1&&ar[c[i]]!=d[i])
		{
			cout << 0 << '\n';
			return;
		}
		ar[c[i]]=d[i];
	}
	if(n<=14)tNk();
	else tAk();
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin >> T;
	while(T--)solve();
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
5
5 1 2
1 2
6 5 2
4 2
5 1
4 2
2 2
2 1
7 1 2
4 1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2
12 2 2
7 2
7 2
*/ 
