#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;

int lis1[MAXN];
int lis2[MAXN];

long long modpow(int a, int b){
	long long r = 1;
	for(int i = 0;i < b;i++){
		r = (r * a) % (1000000007);
	}
	return r;
}

int main(){
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	int T;
	scanf("%d", &T);
	for (int I = 0; I < T; I++){
//		continue;
		int n, m, v;
		scanf("%d%d%d", &n, &m, &v);
		for(int i = 0;i <= n;i++)lis1[i] = 0;
		int x, y, l = false;
		for(int i = 0;i < m;i++){
			scanf("%d%d", &x, &y);
			if(l) continue;
			if(lis1[x] && lis1[x] != y){
				cout << 0 << endl;
				l = true;
			}
			lis1[x] = y;
		}
		if(l) continue;
		// eval
		int r = 0;
		for(int i = 1; i <= v; i++){
			for(int j = 1; j <= v; j++){
				for(int k = 1; k <= n;k++){
					lis2[k] = lis1[k];
				}
				bool l = false;
				for(int k = 1; k < n;k++){
					if(lis2[k] == i){
						if(lis2[k+1] && lis2[k+1] != j) l = true;
						if(l) break;
						lis2[k+1] = j;
					}
				}
				if (l) continue;
//				for (int k = 1; k <= n;k++){
//					if(!lis2[k]) l = true;
//					if(l) break;
//				}
//				if(l) continue;
				r++;
			}
		}
		cout << modpow(r, n - 1)<< endl;
	}
}
