#include<bits/stdc++.h>
#define int unsigned long long
#define MAXN (int)1e5+10
using namespace std;
const int MOD=1e9+7;
int t,n,m,v,c[MAXN],d[MAXN],ans;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
inline int qpow(int x,int y)
{
	int base=x,ret=1;
	while(y)
	{
		if(y&1)
		{
			ret=ret*base%MOD;
		}
		base=base*base%MOD;
		y>>=1;
	}
	return ret;
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	t=read();
	while(t--)
	{
		n=read(),m=read(),v=read();
		if(v<=2)
		{
			puts("0");
			continue;
		}
		for(int i=1;i<=m;i++)
		{
			c[i]=read(),d[i]=read();
		}
		printf("%lld\n",qpow((v*(v-1)%MOD+1),(n-1)));
	}
	return 0;
}
