#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e7+10,M=N*4,mod=1e9+7;
bool mem1;
int T,n,c;
int ifac[N],fac[N];
ll qpow(ll x,ll y=mod-2){
	ll ans=1;
	for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
	return ans;
}
void init(int n=N-1){
	ifac[1]=1;
	for(int i=2;i<=n;i++)ifac[i]=1ll*ifac[mod%i]*(mod-mod/i)%mod;
	for(int i=ifac[0]=1;i<=n;i++)ifac[i]=1ll*ifac[i-1]*ifac[i]%mod;
	for(int i=fac[0]=1;i<=n;i++)fac[i]=1ll*fac[i-1]*(i+i-1)%mod*(i+i)%mod;
}
int C(int n,int m){
	if(0>m||m>n+n)return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n+n-m]%mod;
}
int catalan(int n){
	// debug("catalan",n,(C(n*2,n)-C(n*2,n-1)+mod)%mod);
	return (C(n,n)-C(n,n-1)+mod)%mod;
}
int m,f[N*2];
int s1[N],s2[N];
int calc(int l,int r){
	if(l>r)return 0;
	return (f[r]-f[l-1]+mod)%mod;
}
int solve(int m,int i){
	// debug(m,i,(catalan(m+i-1)-calc(m+1,m+i-2)+mod)%mod);
	return (catalan(m+i-1)-calc(m+1,m+i-2)+mod)%mod;
}
void get(){
	scanf("%d%d",&n,&c),m=n-1;
	for(int i=0;i<=n*2;i++)f[i]=((i?f[i-1]:0)+catalan(i))%mod;
	// debug(ary(f,0,n*2));
	for(int i=s1[0]=1;i<=n;i++)s1[i]=1ll*s1[i-1]*c%mod;
	for(int i=s2[0]=1;i<=n;i++)s2[i]=1ll*s2[i-1]*(c-1)%mod;
	int ans=0;
	for(int i=0;i<n;i++){
		ans=(ans+1ll*solve(n-1-i,i+1)*s1[i]%mod*s2[n-i-1])%mod;
	}
	ans=1ll*ans*c%mod;
	printf("%d\n",ans);
}
bool mem2;
int main(){
	debug(abs(&mem1-&mem2)/1024576.0);
	init();
	for(scanf("%d",&T);T--;)get();
	return 0;
}