#include<bits/stdc++.h>
using namespace std;
const int M=1e3+5,P=1e9+7;
int dp[2][M];
int main(){
	int cas;
	scanf("%d",&cas);
	while(cas--){
		int n,c;
		scanf("%d %d",&n,&c);
		int cur=0;
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=1;i<=2*n;i++){
			int pre=cur;
			cur^=1;
			for(int j=0;j<=i;j++){
				dp[cur][j]=0;
				dp[cur][j]=(dp[cur][j]+dp[pre][j+1])%P;
				if(j>0){
					if(j>1)dp[cur][j]=(dp[cur][j]+1ll*dp[pre][j-1]*(c-1))%P;
					else dp[cur][j]=(dp[cur][j]+1ll*dp[pre][j-1]*c)%P;
				}
				//printf("dp[%d][%d]=%d\n",i,j,dp[cur][j]);
			}
		}
		printf("%d\n",dp[cur][0]);
	}
	return 0;
}