#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
const int N=3e7;
int n,c,jc[N+10],ij[N+10];
void sie(){
    jc[0]=1;
    for(int i=1;i<=N;i++)jc[i]=1ll*i*jc[i-1]%mod;
    ij[N]=qpow(jc[N],mod-2);
    for(int i=N;i;i--)ij[i-1]=1ll*i*ij[i]%mod;
}
int C(int a,int b){
    if(a<b||a<0||b<0)return 0;
    return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;
}
int F(int n,int m){return (C(n*2-m-1,n-1)+mod-C(n*2-m-1,n))%mod;}
int ci[10100000];
void sol(){
    scanf("%d%d",&n,&c);
    ci[0]=1;
    for(int i=1;i<=n;i++)ci[i]=1ll*ci[i-1]*(c-1)%mod;
    int ans=0;
    for(int i=1,w=c;i<=n;i++,w=1ll*w*c%mod)
    (ans+=1ll*F(n,i)*w%mod*ci[n-i]%mod)%=mod;
    printf("%d\n",ans);
}
int main(){
    sie();
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}