#include<bits/stdc++.h>
#define ll long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fd(i,r,l) for(int i=r;i>=l;i--)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
using namespace std;
void read(int&x){
	int b=1;
	char c=getchar();
	while(c<'0'||c>'9')b=(c=='-'?-1:b),c=getchar();
	x=0;
	while(c>='0'&&c<='9')x=x*10+(c^48),c=getchar();
	x*=b;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
ll qp(ll x,int y){
	x%=mod;
	ll ans=1;
	while(y){
		if(y&1)ans=ans*x%mod;
		x=x*x%mod,y>>=1;
	}
	return ans;
}
int n,m,v,c,d,a[20],b[20],tmp[20],ans;
unordered_map<int,int>mp;
void dfs(int x){
	if(x>=n){
		fo(i,1,n){
			tmp[i]=0;
			if(mp[i])tmp[i]=mp[i];
			if(i>1&&tmp[i-1]==a[i-1]){
				if(mp[i]&&tmp[i]!=b[i-1])return;
				tmp[i]=b[i-1];
			}
			if(!tmp[i])tmp[i]=(v==1?1:3-a[i]);
		}
		ans++;
		return;
	}
	fo(i,1,v)fo(j,1,v)a[x]=i,b[x]=j,dfs(x+1);
}
void solve(){
	read(n),read(m),read(v);
	bool flg=1;
	mp.clear();
	fo(i,1,m){
		cin>>c>>d;
		if(!mp[c])mp[c]=d;
		else flg=(mp[c]!=d?0:flg);
	}
	if(!flg)return puts("0"),void();
	if(n==m)return write(qp(v*v-v+1,n-1)),puts(""),void();
	if(v<=2)return ans=0,dfs(1),write(ans),puts(""),void();
}
signed main(){
	freopen("assign.in","r",stdin),freopen("assign.out","w",stdout);
	int _T;read(_T);while(_T--)solve();
	return 0;
}

