#include <bits/stdc++.h>
using namespace std;
int x[1000005], ans;
struct Node {
	int c,d;
} cd[1000005];
const int mod = 1e9 + 7;
bool check(int n) {
	for (int i = 1; i <= n; i++) {
		if (x[cd[i].c] != cd[i].d) {
			return false;
		}
	}
	return true;
}
void build(int a, int b, int n, int v, int pot) {
	if (pot == n) {
		if (check(n)) {
			ans++;
			/*for (int j = 1;j <= n;j++)
			{
				cout << x[j] << " ";
			}
			cout << endl;*/
		}
		return ;
	}
	if (pot == 1) {
		x[pot] = a;
		x[pot + 1] = b;
		for (int aa = 1; aa <= v; aa++) {
			for (int bb = 1; bb <= v; bb++) { //遍历a,b的值
				for (int i = 1; i < n; i++) {
					build(aa, bb, n, v, 2);	//若 xi = ai，则要求 xi+1 = bi，且 ai 与.bi 为.1 到.v 之. 间. 的. 整. 数. ；
					ans %= mod;				//当 xi != ai 时，第i 条限制对 xi+1 的值不做任何约束。
					//除此之外，小 F 还添加了 m 条一元限制，其中第j(1 ≤ j ≤ m) 条限制为：xcj = dj

				}
			}
		}
	} else {
		if (x[pot] == a) {
			x[pot + 1] = b;
		} else {
			for (int aa = 1; aa <= v; aa++) {
				for (int bb = 1; bb <= v; bb++) { //遍历a,b的值
					for (int i = 1; i < n; i++) {
						x[pot + 1] = bb;
						build(aa, bb, n, v, pot + 1); //若 xi = ai，则要求 xi+1 = bi，且 ai 与.bi 为.1 到.v 之. 间. 的. 整. 数. ；
						x[pot + 1] = 0;				  //当 xi != ai 时，第i 条限制对 xi+1 的值不做任何约束。
						ans %= mod;					  //除此之外，小 F 还添加了 m 条一元限制，其中第j(1 ≤ j ≤ m) 条限制为：xcj = dj。

					}
				}
			}
		}
	}
	return ;
}
int main() {
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin >> T;
	while (T--) {
		ans = 0;
		int n, m, v;//n-1条二元限制  m条一元限制
		cin >> n >> m >> v;
		for (int i = 1; i <= m; i++) {
			cin >> cd[i].c >> cd[i].d;
		}
		for (int a = 1; a <= v; a++) {
			for (int b = 1; b <= v; b++) { //遍历a,b的值
				for (int i = 1; i < n; i++) {
					build(a, b, n, v, 1);	//若 xi = ai，则要求 xi+1 = bi，且 ai 与.bi 为.1 到.v 之. 间. 的. 整. 数. ；
					//当 xi != ai 时，第i 条限制对 xi+1 的值不做任何约束。
					//除此之外，小 F 还添加了 m 条一元限制，其中第j(1 ≤ j ≤ m) 条限制为：xcj = dj。
					if (check(n)) {
						ans++;
						/*for (int j = 1;j <= n;j++)
						{
							cout << x[i] << " ";
						}
						cout << endl;*/
					}

				}
				ans %= mod;
			}
		}
		cout << ans << endl;
	}
	return 0;
}
