#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const ll MOD=1e9+7;
int T,n,m;
ll v,a[N],ans;
ll qpow(ll x,int y){
	ll ct=1;
	while(y){
		if((y&1)) ct=ct*x%MOD;
		x=x*x%MOD;
		y=y>>1;
	}
	return ct;
}
bool pd=false;
struct Data{int x,y;}c[N];
void dfs(int pos)
{
	if(pos==n)
	{
		bool pd=false;
		bool f=false;
		if(a[1]==c[1].x) f=true;
		for(int i=2;i<=n;i++)
		{
			int now=0;
			if(f==true){
				if(c[i-1].y!=a[i]&&a[i]!=0){
					pd=true;
					break;
				}
				now=c[i-1].y;
			}
			else now=a[i];
			if(c[i].x==now) f=true;
			else f=false;
		}
		if(pd==false) ans++;
		ans%=MOD;
		return;
	}
	for(int i=1;i<=v;i++)
	{
		for(int j=1;j<=v;j++)
			c[pos]=Data{i,j},dfs(pos+1);
	}
}
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(m==1)
		{
			int c,d;
			for(int i=1;i<=m;i++)
				cin>>c>>d;
			ll ans=1;
			ll x=v*v%MOD;
			ans=qpow(x,n-1);
			cout<<ans<<"\n";
		}
		else if(v<=2)
		{
			for(int i=1;i<=n;i++) a[i]=0;
			bool pd=false;
			for(int i=1;i<=m;i++)
			{
				int c,d;
				cin>>c>>d;
				if(a[c]!=0&&a[c]!=d) pd=true;
				a[c]=d;
			}
			if(pd==true){
				cout<<"0\n";
				continue;
			}
			ans=0;
			dfs(1);
			cout<<ans<<"\n";
		}
	}
	return 0;
}
