#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1000010,mod=1e9+7;
typedef long long ll;
int n,m,v;
int tag[N];
int way[N];
int a[N],b[N];
bool flag;
int cnt;

void dfs_way(int u)
{
	if (flag) return;
	if (u>n)
	{
		for (int i=1;i<=n-1;i++)
		{
			if (way[i]==a[i] && way[i+1]!=b[i])
			{
				return;
			}
		}
		flag=true;
		return;
	}
	if (tag[u]!=-1)
	{
		way[u]=tag[u];
		dfs_way(u+1);
	}
	else
	{
		for (int i=1;i<=v;i++)
		{
			way[u]=i;
			dfs_way(u+1);
		}
	}
}

void dfs(int u)
{
	if (u==n)
	{
		flag=false;
		dfs_way(1);
		if (flag) cnt=(cnt+1)%mod;
		return;
	}
	for (int i=1;i<=v;i++)
	{
		for (int j=1;j<=v;j++)
		{
			a[u]=i;
			b[u]=j;
			dfs(u+1);
		}
	}
}

int qmi(ll a,int b,int p)
{
	ll res=1;
	while (b)
	{
		if (b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}

void solve1()
{
	int res=qmi(1ll*v*v-v+1,n-1,mod);
	cout << res << "\n";
}

int main()
{	
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	
	int T;
	cin >> T;
	while (T--)
	{
		cin >> n >> m >> v;
		
		memset(tag,-1,sizeof(tag));
		bool f0=true;
		bool fla1=true;
		fla1&=(n==m);
		for (int i=1;i<=m;i++)
		{
			int p,w;
			cin >> p >> w;
			fla1&=(p==i);
			if (tag[p]!=-1 && tag[p]!=w)
			{
				f0=false;
				break;
			}
			tag[p]=w;	
		}
		if (!f0)
		{
			cout << "0\n";
			continue;
		}
		if (fla1)
		{
			solve1();
			continue;
		}
		cnt=0;
		dfs(1);
		cout << cnt << "\n";
	}
	return 0;
}
