#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int mod = 1e9+7;

int pw(int x,int k)
{
	int re=1;
	for(;k;k>>=1,x=1ll*x*x%mod) if(k&1)
		re=1ll*re*x%mod;
	return re;
}
int inv(int a){return pw(a,mod-2);}

const int maxn = 2e7+10;
signed fac[maxn],ifac[maxn];
int C(int n,int m)
{
	if (m<0 || m>n) return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int Catalan(int n){
	return 1LL*fac[2*n]*ifac[n] % mod*ifac[n+1] % mod;	
}

signed main()
{
	ios_base::sync_with_stdio(false);
	
	fac[0]=1; for(int i=1;i<maxn;i++) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[maxn-1]= pw(fac[maxn-1],mod-2);
	for(int i=maxn-2;i>=0;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		int n,c;
		cin>>n>>c;
		if (c==1){
			cout << 1 << "\n";
			continue;	
		}
		vector<int> pw(n+2);
		int ttt=1LL*c*c % mod *inv(c-1)%mod;
		pw[0]=1;
		for (int i=1;i<=n+1;i++) pw[i]=1LL*pw[i-1]*ttt%mod;
		int ans=0;
		for (int k=0;k<=n;k++){
			int A=1;
			if (k>0) A=(mod-1LL*c*Catalan(k-1)%mod)%mod;
			int B=pw[n-k];
			ans=(ans+1LL*A*B)%mod;
		}
		cout << ans << "\n";
	}
	
	return 0;
}