#include <bits/stdc++.h>
#define ll int
#define LL long long
#define Ma 20000005
#define mod 1000000007
#define N 1005
#define pb push_back
#define ls p<<1
#define rs p<<1|1
using namespace std;
ll mul[Ma],pre[Ma];
ll n,k;
ll po(ll p,ll x=mod-2)
{
	ll sum=1;
	while (x)
	{
		if (x&1) sum=1ll*sum*p%mod;
		p=1ll*p*p%mod;
		x>>=1;
	}
	return sum;
}

void pri()
{
	mul[0]=1;
	for (ll i=1;i<Ma;i++)
		mul[i]=1ll*mul[i-1]*i%mod;
	pre[Ma-1]=po(mul[Ma-1]);
	for (ll i=Ma-2;i>=0;i--)
		pre[i]=1ll*pre[i+1]*(i+1)%mod;
	return;
}

ll C(ll x,ll y)
{
	if (x<0||y<0||x>y) return 0;
	return 1ll*mul[y]*pre[x]%mod*pre[y-x]%mod;
}



void sol()
{
	cin>>n>>k;
	if (k==1)
	{
		printf("1\n");
		return;
	}
	ll ans=0,l=1,r=po(k-1,n),inv=po(k-1);
	for (ll i=1;i<=n;i++)
	{
		l=1ll*l*k%mod;
		r=1ll*r*inv%mod;
		ans=(ans+1ll*l*r%mod*C((i-1)*2,(n-1)*2)%mod)%mod;
	}
	printf("%d\n",ans);
}

int main()
{
	pri();
	ios::sync_with_stdio(0); cin.tie(0);
	ll tt;
	cin>>tt;
	while (tt--)
		sol();
	return 0;
}