#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int NN=1e9+7;
int n,c,f[100100];
int p[100100],ni[100100];
int cc(int x){
    return p[2*x]*ni[x+1]%NN*ni[x]%NN;
}
int mi(int x,int y){
    int sum=1;
    for (;y;y>>=1,x=x*x%NN)
    if(y&1)sum=sum*x%NN;
    return sum;
}
int pp[100100];
void solve(){
    cin>>n>>c;//n*=2;
    p[0]=1;
    for (int i=1;i<=2*n;i++)
    p[i]=p[i-1]*i%NN;
    ni[2*n]=mi(p[2*n],NN-2);
    for (int i=2*n;i;i--)
    ni[i-1]=ni[i]*i%NN;
    f[0]=1;
    pp[0]=1;
    for (int i=1;i<=n;i++)
    pp[i]=pp[i-1]*(c-1)%NN;
    for (int i=1;i<=n;i++){
        f[i]=0;
        for (int j=0;j<i;j++)
        f[i]=(f[i]+f[j]*cc(i-j-1)%NN*pp[i-j-1]%NN*c)%NN;
    }
    cout<<f[n]<<"\n";
}
signed main(){
    int T;cin>>T;
    while(T--)solve();
}