#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int maxn=1e5+5;
int t;
int c[maxn],d[maxn];
ll powmod(ll x,ll y)
{
	ll sum=1;
	while(y)
	{
		if(y&1)
			sum=sum*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return sum;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--)
	{
		int n,m,v;
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++)
			cin>>c[i]>>d[i];
		if(m==n)
		{
			ll ans=1,sum=1;
			for(int i=2;i<=m;i++)
			{
				sum=sum*(v-1)%mod;
				ans=(ans+sum)%mod;
			}
			cout<<ans<<"\n";
		}
		else
			cout<<"0\n";
	}
	return 0;
}
