#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 7,mod = 1e9 + 7;

typedef long long ll;
typedef pair<ll,ll> pii;


ll n,m,v;
pii sgl[N];
ll qmi(ll a,ll k){//a^k % mod
	ll res = 1;
	while(k){
		if(k & 1) res = res * a % mod;
		a = a * a % mod;
		k >>= 1;
	}
	return res;
}
namespace nsp1{
	int num[14];
	bool check(int st_a,int st_b){
		int a[14],b[14];
		for(int i = 1;i < n;i++) a[i] = (st_a >> (i - 1)) & 1,b[i] = (st_b >> (i - 1)) & 1;
		for(int i = 1;i < n;i++) a[i]++,b[i]++; 
		for(int i = 1;i < n;i++)
			if(num[i] == 0) continue;
			else if(num[i] == 1){
				if(num[i] != a[i]) continue;
				if(b[i] == num[i + 1] || num[i + 1] == 0) continue;
				return false;
			}
			else{
				if(num[i] != a[i]) continue;
				if(b[i] == num[i + 1] || num[i + 1] == 0) continue;
				return false;
			}
		return true;
	}
	void proc(){
		ll ans = 0;
		for(int i = 1;i <= n;i++) num[i] = 0;
		for(int i = 1;i <= m;i++) num[sgl[i].x] = sgl[i].y;
		
		for(int st_a = 0;st_a < 1 << (n - 1);st_a++)
			for(int st_b = 0;st_b < 1 << (n - 1);st_b++)
				if(check(st_a,st_b)) ans++;
		cout << ans << endl;
	}
}
namespace nsp2{
	void proc(){
		ll sqv = v * v % mod;
		cout << qmi(sqv,n - 1) << endl;
	}
}
namespace nsp3{
	void proc(){
		ll every = v * v % mod - v + 1;
		every = (every % mod + mod) % mod;
		cout << qmi(every,n - 1) << endl;
	}
}
void work(){
	cin >> n >> m >> v;
	for(int i = 1;i <= m;i++) cin >> sgl[i].x >> sgl[i].y;
	sort(sgl + 1,sgl + m + 1);
	
	
	//special cases.
	for(int i = 1;i < m;i++)
		if(sgl[i].x == sgl[i + 1].x && sgl[i].y != sgl[i + 1].y){
			cout << "0" << endl;
			return;
		} 
		
	if(m == 1 || m == 0) nsp2::proc();//ok.
	else if(v <= 2) nsp1::proc();
	else if(m == n) nsp3::proc();//ok.
	else{
		
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	
	int _;cin >> _;
	while(_--) work();
	
	flush(cout);
	fclose(stdin),fclose(stdout); 
	
	return 0;
}

