#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5 + 5,mod = 1e9 + 7;
int c[N],d[N],fac[N],inv[N],x[20];
int qmi(int a,int b){
	int res = 1;
	while(b){
		if(b & 1) res = 1ll * res * a % mod;
		b >>= 1;
		a = 1ll * a * a % mod;
	}
	return res;
}
int C(int a,int b){
	return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	fac[0] = 1;
	for(int i=1;i<N;i++){
		fac[i] = 1ll * fac[i - 1] * i % mod;
//		cout<<fac[i]<<" ";
	}
	inv[N - 1] = qmi(fac[N - 1],mod - 2);
	for(int i=N - 2;i>=0;i--){
		inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
//		cout<<inv[i]<<" ";
	}
//	cout<<C(1,0)<<endl;
	
	int T;
	cin>>T;
	while(T--){
		
		int n,m,v;
		cin>>n>>m>>v;
		bool flaga = n == m;
		for(int i=1;i<=m;i++){
			cin>>c[i]>>d[i];
			flaga &= c[i] == i;
		}
		if(n <= 12 && m <= 12 && v <= 2){
//			cout<<"!!!\n";
			int res = 0;
			for(int i=0;i<=(1 << n - 1) - 1;i++){
				for(int j=0;j<=(1 << n - 1) - 1;j++){
//					cout<<i<<" "<<j<<'\n';
					bool flag = true;
					memset(x,0,sizeof(x));
					for(int k=1;k<=m;k++){
						if(x[c[k]]){
							flag = false;
							break;
						}
						x[c[k]] = d[k];
					}
					for(int k=0;k<n - 1;k++){
						if(x[k + 1] == (i & (1 << k)) + 1){
							if(x[k + 2] && x[k + 2] != (j & (1 << k)) + 1){
								flag = false;
								break;
							}
							x[k + 2] = (j & (1 << k)) + 1;
						}
					}
					res += flag;
				}
			}
			cout<<res<<'\n'; 
		}else if(flaga){
			int res = 0;
			for(int i=0;i<n;i++){
				res = (res + 1ll * C(n - 1,i) * qmi((1ll * v * (v - 1) % mod),i) % mod) % mod;
			}
			cout<<res<<'\n';
		}else{
			cout<<0<<'\n';
		}
	}
	return 0;
}
/*
1
2 1 2
1 1
*/
