#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (int i=s;i<=t;i++)
#define pi acos(-1)
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef pair<PII, PII> PPP;
typedef pair<PII, int> PPI;
#define repp(i,s,t) for (int i=s;i>=t;i--)
template<class T> T sqr(T x) {return x*x;}
#define debug(x) cerr<<#x"="<<(x)<<endl;
#define pb(x) push_back(x);
#define ori(x) x-'a'
const LL mod = 1e9 + 7;
LL f[2001][2011];
LL M[3001];
int n, m;
int main()
{
	int testdata;
	scanf("%d",&testdata);
	while (testdata--)
	{
		scanf("%d%d",&n,&m);
		f[0][0] = 1;
		M[0] = 1;
		rep(i,1,n)
		{
			M[i] = (M[i-1] * m) % mod;
			int mm = min(m, i);
			rep(j,0,mm)
			{
				f[i][j] = 0;
				if (j) f[i][j] = (f[i][j] + f[i-1][j-1] * (m - j + 1)) % mod;
				if (j + 1 <= m) f[i][j] = (f[i][j] + f[i-1][j+1] * (j + 1)) % mod;			
			}		
		}
		LL ans = 0;
		rep(i,1,n) ans = (ans + f[i][i & 1] * (n - i + 1) % mod * M[n - i]) % mod;
		printf("%lld\n", ans);
	}
}