#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int n, m, v, val[N];
long long ans = 0;

void Set(){
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

void Init(){
	memset(val, 0, sizeof(val));
	ans = 0;
	int c, d;
	cin >> n >> m >> v;
	for(int i = 1; i <= m; i++){
		cin >> c >> d;
		if(val[c]) ans = -1;
		val[c] = d;
	}
}

void SolveA(){
	ans = 1;
	for(int i = 1; i < n; i++){
		ans = (ans * (n * (n-1) + 1)) % MOD;
	}
}

void SolveS(){
	ans = 1;
	for(int i = 1; i < n; i++){
		if(val[i] == 1 && val[i+1] == 2) ans *= 3;
		else if(val[i] == 2 && val[i+1] == 1) ans *= 3;
		else if(val[i+1] != 0) ans *= 4;
		else ans *= 4;
	}
}

int main(){
	Set();
	int t;
	cin >> t;
	while(t--){
		Init();
		if(ans == -1) ans = 0;
		else if(n <= 12 && m <= 12 && v <= 2) SolveS();
		else SolveA();
		cout << ans << "\n";
	}
	return 0;
}
