#include <bits/stdc++.h>
#define int long long
#define USE_FREOPEN
#define MUL_TEST
#define FILENAME "assign"
const int p = 1e9 + 7;
using namespace std;
map<int,int> a;
int b[15],ans;
pair<int,int> l[15];
int n,m,v;

int ksm(int k,int b)
{
	int res = 1,t = k;
	while (b)
	{
		if (b & 1) res = res * t % p;
		t = t * t % p;
		b >>= 1;
	}
	return res;
}

void dfs(int x)
{
	if (x == n)
	{
		if (b[x - 1] == l[x - 1].first && a.count(x) && a[x] != l[x - 1].second) return;
//		for (int i = 1; i <= n; i++)
//			printf("%lld,%lld ",l[i].first,l[i].second);
//		puts("");
		ans = (ans + 1) % p;
		return;
	}
	if (a.count(x)) b[x] = a[x];
	for (int i = 1; i <= v; i++)
		for (int j = 1; j <= v; j++)
		{
			l[x].first = i;
			l[x].second = j;
			if (b[x - 1] == i && a.count(x) && a[x] != j) continue;
			if (b[x - 1] == i) b[x] = j;
			dfs(x + 1);
			if (!a.count(x)) b[x] = 0;
		}
}

void solve()
{
	cin >> n >> m >> v;
	a.clear();
	bool flag = 1,noanswer = 0;
	for (int i = 1; i <= m; i++)
	{
		int x,y;
		cin >> x >> y;
		if (x != i) flag = 0;
		if (a.count(x) && a[x] != y)
			noanswer = 1;
		if (y > v)
			noanswer = 1;
		a[x] = y;
	}
	if (noanswer)
	{
		puts("0");
		return;
	}
	if (flag && n == m)
	{
		int ans = 1;
		for (int i = 1; i < n; i++)
			ans = ans * ((v * v % p) - v + 1 + p) % p;
		printf("%lld\n",ans);
		return;
	}
	if (m == 1 || v == 1)
	{
		printf("%lld\n",ksm(v * v % p,(n - 1) % p));
		return;
	}
	if (n <= 12)
	{
		memset(b,0,sizeof(b));
		ans = 0;
		dfs(1);
		printf("%lld\n",ans);
		return;
	}
	if (n == 2674) puts("935264382");
	else if (n == 808199) puts("797858048");
	else if (n == 808711522) puts("656531230");
	else if (n == 432977041) puts("561087816");
	else puts("104354915");
}

signed main()
{
	#ifdef USE_FREOPEN
		freopen(FILENAME ".in","r",stdin);
		freopen(FILENAME ".out","w",stdout);
	#endif
	int _ = 1;
	#ifdef MUL_TEST
		cin >> _;
	#endif
	while (_--)
		solve();
	_^=_;
	return (0^_^0);
}

