#include "bits/stdc++.h"
typedef std::pair<int,int> pii;
typedef long long ll;
const int MAXN = 111,mod = 1e9+7;
int f[MAXN][MAXN];
int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int task;std::cin>>task;
    while(task--)
    {
        int n,c;std::cin>>n>>c;
        f[0][0]=1;
        for(int i=1;i<=n*2;++i)
            for(int j=0;j<=n;++j)
            {
                f[i][j]=0;
                if(j>=1)f[i][j]=ll(f[i-1][j-1])*(j==1?c:c-1)%mod;
                f[i][j]=(f[i][j]+f[i-1][j+1])%mod;
            }
        printf("%d\n",f[n*2][0]);
    }
    return 0;
}