#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const long long mod=1e9+7;
const int M=1e5+5;
long long n,m,v;
int c[M],d[M];
long long fw(long long a,long long b)
{
	long long base=1;
	while(b)
	{
		if(b%2)base=(base*a)%mod;
		b>>=1,base=(base*base)%mod;
	}
	return base;
}
void solve1()
{
	cout<<fw(1+(n-1)*n,n-1)<<"\n";
	return ;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{	
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&c[i],&d[i]);
		}
		solve1();
	}
	return 0;
}
