#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
const ll mod=1e9+7;
int T,n,m,V,as[20];
int w[20],a[20],b[20];
struct chat{ 
	int c,d;
} l[MAXN];
int cmp(chat x,chat y) 
{ 
	if(x.c!=y.c) return x.c<y.c;
	else return x.d<y.d;
} 
void solve1() 
{ 
	bool op=false;
	for(int i=1;i<=n;++i) w[i]=-1;
	for(int i=1;i<=m;++i) 
	{ 
		cin>>l[i].c>>l[i].d;
		if(w[l[i].c]!=-1&&w[l[i].c]!=l[i].d) 
			op=true;
		w[l[i].c]=l[i].d;
	} 
	if(op) { 
		cout<<"0\n";
		return ;} 
	ll sum=0;
	for(int i=0;i<(1<<(n-1));++i) 
	{ 
		for(int k=1;k<n;++k) 
			a[k]=((i>>(k-1))&1)+1;
		for(int j=0;j<(1<<(n-1));++j) 
		{ 
			for(int k=1;k<=n;++k) as[k]=w[k];
			for(int k=1;k<n;++k) 
				b[k]=((j>>(k-1))&1)+1;
			op=true;
			for(int k=1;k<n;++k) 
			{ 
				if(w[k]!=-1&&as[k]!=w[k]) { 
					op=false;break;} 
				if(as[k]==a[k]) as[k+1]=b[k];
			} 
			if(w[n]!=-1&&as[n]!=w[n]) op=false;
			if(op) ++sum;
		} 
	} 
	cout<<sum%mod<<"\n";
} 
ll fast(ll x,ll k) 
{ 
	ll ans=1;
	while(k) 
	{ 
		if(k%2==1) ans=ans*x%mod;
		x=x*x%mod;
		k/=2;
	} 
	return ans;
} 
void solve2() 
{ 
	for(int i=1;i<=m;++i) 
		cin>>l[i].c>>l[i].d;
	cout<<fast(1ll*V*V%mod,n-1)<<"\n";
} 
void solve3() 
{ 
	for(int i=1;i<=m;++i) 
		cin>>l[i].c>>l[i].d;
	cout<<fast((1ll*V*(V-1)+1)%mod,n-1)<<"\n";
} 
int main() 
{ 
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) 
	{ 
		cin>>n>>m>>V;
		if(V==2) { 
			solve1();
			continue;} 
		if(m==1) { 
			solve2();
			continue;} 
		if(n==m) { 
			solve3();
			continue;} 
	} 

	return 0;
} 
