#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define in(a, b) for (ll i = (a); i <= (b); i++)                // in using i
#define inj(a, b) for (ll j = (a); j <= (b); j++)               // in using j
#define ink(a, b) for (ll k = (a); k <= (b); k++)               // in using k
#define inl(a, b) for (ll l = (a); l <= (b); l++)               // in using l
#define inr(a, b) for(ll i = (a); i >= (b); i--)                // in reverse
#define inrj(a, b) for(ll j = (a); j >= (b); j--)                // in reverse
#define inrk(a, b) for(ll k = (a); k >= (b); k--)                // in reverse
#define inrl(a, b) for(ll l = (a); l >= (b); l--)                // in reverse
#define tt ll tcs; cin>>tcs; while(tcs--)                       // include test cases
#define ina(arr,n) ll arr[(n+1)]={0}; in(1,n) cin>>arr[i]       // input arr of n elements
#define inv(vec,n) vector<ll> vec(n+1); vec[0]=0; in(1,n) cin>>vec[i]; // input vector of n elements
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pll pair <ll,ll>
#define vpll vector <pll>
#define sll set <ll>
//Dont forget to reset MOD if some other MOD is needed
const ll MOD = 1e9+7;
 
//Comment the line above and uncomment the line below if problem requires more than 1 MOD
//After uncommenting the below line, declaration of mint becomes [ mint<mod> M; ]
 
//template<ll MOD>
class mint
{
    //WARNING:
    //Be very careful not to use two mints with different mods for any operation
    //No guarantee of behavior in this case
    public:
    ll val;
    static ll mod_exp(ll a, ll b){ ll res=1;   a=a%MOD; while(b>0){ if(b%2==1) res=(res*a)%MOD; b/=2; a=(a*a)%MOD; } return res; }
    static ll gcdExtended(ll a, ll b, ll *x, ll *y) { if (a == 0) { *x = 0, *y = 1; return b; } ll x1, y1; ll gcd = gcdExtended(b%a, a, &x1, &y1);*x = y1 - (b/a) * x1; *y = x1; return gcd; }
    static ll modInverse(ll a) { ll x, y; 	ll g = gcdExtended(a, MOD, &x, &y); g++; ll res = (x%MOD);	if(res < 0) res += MOD;	return res;} 
    mint(){	val = 0;} 
    mint(ll x){	val = x%MOD;	if(val < 0) val += MOD;}
    mint& operator +=(const mint &other){	val += other.val;	if(val >= MOD) val -= MOD; return (*this); }
    mint& operator -=(const mint &other){   val -= other.val;if(val < 0) val += MOD;  return (*this); }
    mint& operator *=(const mint &other){	val = (val * other.val)%MOD; return (*this); }
    mint& operator /=(const mint &other){	val = (val * modInverse(other.val)) % MOD; return (*this); }
    mint& operator =(const mint &other) { 	val = other.val; return (*this); }
    mint operator +(const mint &other) const {	return mint(*this) += other; }
    mint operator -(const mint &other) const {	return mint(*this) -= other; }
    mint operator *(const mint &other) const {	return mint(*this) *= other; }
    mint operator /(const mint &other) const {	return mint(*this) /= other; }
    bool operator ==(const mint &other) const {   return val == other.val; }
 
    mint operator ++() { ++val; if(val == MOD) val = 0; return (*this); }
    mint operator ++(int) { val++; if(val == MOD) val = 0; return mint(val-1); }
    mint operator --() { --val; if(val == -1) val = MOD-1; return (*this); }
    mint operator --(int) { val--; if(val == -1) val = MOD-1; return mint(val+1); }
 
    // ^ has very low precedence, careful!!
 
    template<typename T>
    mint& operator ^=(const T &other){   val = mod_exp(val, other); return (*this); }
    template<typename T>
    mint operator ^(const T &other) const {  return mint(*this) ^= other; }
 
    mint& operator ^=(const mint &other){   val = mod_exp(val, other.val); return (*this); }
    mint operator ^(const mint &other) const {  return mint(*this) ^= other; }
 
    template<typename T>
    explicit operator T() {	return (T)val; }
    template<typename T>
    friend mint operator +(T other, const mint &M){	return mint(other) + M; }
    template<typename T>
    friend mint operator -(T other, const mint &M){	return mint(other) - M; }
    template<typename T>
    friend mint operator *(T other, const mint &M){	return mint(other) * M; }
    template<typename T>
    friend mint operator /(T other, const mint &M){	return mint(other) / M; }
    template<typename T>
    friend mint operator ^(T other, const mint &M){	return mint(other) ^ M; }
 
 
    friend std::ostream &operator << (std::ostream &output, const mint &M){  return output << M.val; }
    friend std::istream &operator >> (std::istream &input, mint &M) { input >> M.val;	M.val %= MOD;	return input;}
};
#define vll vector<mint>
#define mll map <ll,ll>
#define all(x) x.begin(), x.end()
const ll mod=1e9+7;
#define vvll vector<vll>
#define pref(p,a,n) vll p(n+1); in(1,n) p[i]=p[i-1]+a[i];
#define vec2(a,n,m) vvll a(n+1,vll(m+1))
// #define vec2(a,n,m,val) vvll a(n+1,vll(m+1,val))

#define vec3(a,l,m,n) vector<vvll>a(l+1,vvll(m+1,vll(n+1)));
// #define vec3(a,l,m,n,val) vector<vvll>a(l+1,vvll(m+1,vll(n+1,val)));
# define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main(){
    FAST
    tt{
        ll n,c;
        cin>>n>>c;
        vec2(dp,2*n,n);
        dp[0][0]=1;
        in(1,2*n){
            for(ll j=0;j<=n;j++){
                if(j==0){
                    dp[i][1]=dp[i-1][0]*c;
                }
                else{
                    dp[i][j+1]+=dp[i-1][j]*(c-1);
                    dp[i][j-1]+=dp[i-1][j];
                }
            }
        }
        cout<<dp[2*n][0]<<endl;
    }
}