#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
struct Node{
	int x,y;
	friend bool operator < (Node a,Node b){
		return a.x < b.x;
	} 
}a[500006];
int n,m,v,T,vis[5006],A[16],B[16],ans = 0,f[10000006][2]; 
int power(int a,int b){
	int o = 1;
	while(b){
		if(b&1) o = o*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return o;
}
void dfs(int x){
	if(x == n){
		int p[16];
		for(int i = 1;i <= n; i++)
			p[i] = vis[i];
		for(int i = 1;i < n; i++){
			if(p[i]){
				if(A[i] == p[i]){
					if(p[i+1]){
						if(p[i+1] != B[i])
							return ; 
					}else
						p[i+1] = B[i];
				}
			}
		}
		ans++;
		return ;
	}
	for(int i = 1;i <= v; i++)
		for(int j = 1;j <= v; j++){
			A[x] = i,B[x] = j;
			dfs(x+1);
			A[x] = 0,B[x] = 0;
		}
} 
void solve(){
	memset(a,0,sizeof(a));
	memset(vis,0,sizeof(vis));
	n = 0,m = 0,v = 0;a[0].x = 0;ans = 0;
	cin >> n >> m >> v;
	bool flag1 = (m == n);
	for(int i = 1;i <= m; i++){
		cin >> a[i].x >> a[i].y;
		if(a[i].x != i) flag1 = 0;
	}
	if(v <= 2){
		int x = 0,y = 0;
		for(int i = 1;i <= m; i++){
			x = a[i].x,y = a[i].y;
			if(vis[x] &&vis[x] != y){
				cout << 0 << endl;
				return ;
			}
			vis[x] = y;
		}
		dfs(1);
		cout << ans << endl;
		return ;
	}
	sort(a+1,a+1+m);
	for(int i = 1;i <= m; i++)
		if(a[i].x == a[i-1].x&&a[i].y != a[i-1].y){
			cout << 0 << endl;
			return ;
		}
	if(flag1){
		v %= mod;
		f[0][0] = 1;
		for(int i = 1;i < n; i++)
		{
			f[i][0] = (f[i-1][1]+f[i-1][0])*(v-1)%mod*v%mod;
			f[i][1] = (f[i-1][1]+f[i-1][0])%mod;
		}
		cout << (f[n-1][0]+f[n-1][1])%mod << endl;
		return ;
	} 
	v %= mod;
	int ans = 1;
	a[0].x = 1;
	for(int i = 1;i <= m; i++){
		if(i > 1&&a[i].x-1 == a[i-1].x)
			ans = (ans*((v*(v-1)%mod+1)%mod)%mod)%mod;
		else ans = (ans*power(v,2*(a[i].x-a[i-1].x)%mod))%mod;
	}
	cout << ans*power(v,2*(n-a[m].x)%mod)%mod  << endl;
}
main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin >> T;
	while(T--)
		solve();
	return 0;
}
