#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, m, v, ans;
int w[N], tmp[N], a[N], b[N];

int qpow(int a, int k)
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		k >>= 1;
	}
	return res;
}

void dfs(int u)
{
	if (u == n)
	{
		for (int i = 1; i <= n; i++) tmp[i] = w[i];
		for (int i = 1; i < n; i++)
			if (tmp[i] == a[i])
			{
				if (tmp[i + 1])
				{
					if (tmp[i + 1] != b[i]) return;
				}
				else tmp[i + 1] = b[i];
			}
		ans++;
		return;
	}
	for (int i = 1; i <= v; i++)
		for (int j = 1; j <= v; j++)
		{
			a[u] = i, b[u] = j;
			dfs(u + 1);
		}
}

void sol()
{
	memset(w, 0, sizeof w);
	memset(a, 0, sizeof a);
	memset(b, 0, sizeof b);
	scanf("%d%d%d", &n, &m, &v);
	bool check = false;
	for (int i = 1; i <= m; i++)
	{
		int c, d;
		scanf("%d%d", &c, &d);
		if (w[c]) check = true;
		w[c] = d;
	}
	if (check)
	{
		puts("0");
		return;
	}
	if (m == 1)
	{
		printf("%d\n", qpow(v, (n - 1) * 2));
		return;
	}
	ans = 0;
	dfs(1);
	printf("%d\n", ans);
}

signed main()
{
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T--) sol();
	return 0;
}
