#include"bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(),(x).end()
const int mod=1e9+7;
void init(int n)
{ }
void upd(int &x,int y) { x=(x+y)%mod; }
int f[100][100];
void solve()
{
	int n,c; cin>>n>>c;
	f[0][0]=1;
	for (int i=0; i<n*2; ++i)
	{
		for (int j=0; j<=i; ++j)
		{
			if (j>0) upd(f[i+1][j-1],f[i][j]);
			else upd(f[i+1][j+1],f[i][j]*(j==0?c:c-1));
		}
	}
	cout<<f[n*2][0]<<'\n';
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int T=0; cin>>T;
	init(1000'0000);
	while (T--)
	{
		solve();
	}
}