#include<bits/stdc++.h>
using namespace std;
int c[100010] = {};
int d[100010] = {};
bool eee[100010] = {}; 
long long mo = 1000000009;
int main() {
	freopen("assign.in ", "r", stdin);
	freopen("assign.out", "w", stdout);
	int t = 0;
	cin >> t;
	while(t--) {
		fill(eee, eee + 100010, false);
		long long ans = 1;
		int n = 0;
		int m = 0;
		int v = 0;
		cin >> n >> m >> v;
		for (int i = 1; i <= m; ++i) {
			cin >> c[i] >> d[i];
			if(eee[c[i]]) ans = 0;
			eee[c[i]] = true;
		}
		if(ans == 0) {
			cout << 0 << endl;
		}
		else if(v <= 2) {
			ans = 1;
			for (int i = 1; i < n; ++i) {
				if(eee[i] && eee[i + 1]) {
					ans *= 3;
					ans %= mo;
				}
				else {
					ans *= 4;
					ans %= mo; 
				}
			}
			cout << ans % mo << endl;
		}
		else if(m == n){
			ans = 1;
			for (int i = 1; i < n; ++i) {
				ans *= (v - 1) % mo;
				ans %= mo;
				ans *= v % mo;
				ans %= mo;
			}
			long long eee = v;
			for (int i = 1; i < n; ++i) {
				ans += ans / eee;
				ans %= mo;
				eee *= v;
				eee %= mo;
			}
			cout << ans % mo << endl;
		}
	}
	
	return 0;
}
