#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 10,mod = 1e9 + 7;
int c[maxn],d[maxn];
int a[maxn];
int b[maxn],e[maxn];
int n,m,v;
int calc(){
	for(int i = 1;i < n;i++)
		if(a[i] == b[i]){
			if(a[i+1] && a[i+1] != e[i])return 0;
			a[i+1] = d[i];
		}
	return true;
}
int dfs(int x){
	if(x >= n){
		memset(a+1,0,n << 2);
		for(int i = 1;i <= n;i++)a[c[i]] = d[i];
		if(a[1])return calc();
		int ans = 0;
		for(int i = 1;i <= v;i++)ans = (ans + calc()) % mod;
		return ans; 
	}
	int ans = 0;
	for(b[x] = 1;b[x] <= v;b[x]++)
		for(e[x] = 1;e[x] <= v;e[x]++)
			ans = (ans + dfs(x + 1)) % mod;
	return ans;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&v);
		bool flag = n == m;
		set<int> s;
		bool flag2 = true;
		for(int i = 1;i <= m;i++){
			scanf("%d%d",c+i,d+i);
			flag &= i == c[i];
			if(s.find(c[i]) != s.end() && flag2){
				puts("0");
				flag2 = false;
			}
			s.insert(c[i]);
		}
		if(!flag2)puts("0");
		else if(flag)cout << ((n - 1ll) * ((v * (v - 1ll) % mod + 1) % mod) % mod) % mod << '\n';
		else printf("%d\n",dfs(1));
	}
}
