#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int N = 1e5+10 , M = 1e3 , mod = 1e9+7 ;
int T , n , m , v ;
int c[N] , d[N] , x[N] ;
bool vis[N] , flag ;
ll f[M] ; // f[u][0/1]:表示第u个数的值是任取或定值的方案数。 
ll ans = 0 ;
void init(){
	memset(vis , false , sizeof(vis)) ;
	memset(f , 0 , sizeof(f)) ;
	memset(x , 0 , sizeof(x)) ;
	flag = true ;
}
ll quick_pow(ll a , int b){
	ll sum = 1 , aa = a % mod ;
	while(b){
		if(b & 1) sum = sum*aa%mod ;
		b >>= 1 ;
		aa = aa*aa%mod ;
	}
	return sum ;
}
int main(){
	freopen("assign.in" , "r" , stdin) ;
	freopen("assign.out" , "w" , stdout) ;
	scanf("%d", &T) ;
	while(T--){
		init() ;
		scanf("%d%d%d", &n , &m , &v) ;
//		cout << 11111 << endl ;
		for(int i = 1 ; i <= m ; i++){
//			cout << i << endl ;
			scanf("%d%d", &c[i] , &d[i]) ;
//			x[c[i]] = d[i] ;
		}
		printf("%lld\n", quick_pow(((ll)(v-1)*v+1) , n-1)) ;
		
	}
	return 0 ;
}
/*

*/

