#include <bits/stdc++.h>
using namespace std;
#define out(x) cerr << #x << " = " << x << " "
#define outln(x) cerr << #x << " = " << x << endl
#define outarr(x, l, r) {cerr << #x"[" << l << "~" << r << "] = "; for (int _ = l; _ <= r; ++_) cerr << x[_] << " "; cerr << endl;}
typedef long long ll;
const int mod = 1000000007;
struct Z {
	int x;
	Z(int _ = 0):x(_) {}
};
Z operator + (const Z &a, const Z &b) {int x = a.x + b.x; return x >= mod ? x - mod : x;}
Z operator - (const Z &a, const Z &b) {int x = a.x - b.x; return x < 0 ? x + mod : x;}
Z operator * (const Z &a, const Z &b) {return (ll)a.x * b.x % mod;}
Z& operator += (Z &a, const Z &b) {return a = a + b;}
Z& operator -= (Z &a, const Z &b) {return a = a - b;}
Z& operator *= (Z &a, const Z &b) {return a = a * b;}
ostream& operator << (ostream &os, const Z &a) {os << a.x; return os;}
Z qpow(Z a, int b) {Z ans = 1; while (b) {if (b & 1) ans *= a; a = a * a; b >>= 1;} return ans;}

const int N = 20000005;
Z fac[N], ifac[N], inv[N];
Z binom(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return fac[n] * ifac[m] * ifac[n - m];
}

void prepare(int n) {
	fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
	inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = inv[mod % i] * (mod - mod / i);
	ifac[0] = 1; for (int i = 1; i <= n; ++i) ifac[i] = ifac[i - 1] * inv[i];
}

int n, c;
Z pw0[N], pw1[N];

Z calc(int n, int k) {
	//[x ^ n] (C(x) ^ k), where C(x) represents the OGF of Catalan numbers.
	Z val = binom(n + n + k - 1, n) - binom(n + n + k - 1, n - 1);
	return val;
}

int main() {
	prepare(20000003);
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &c);
		Z ans = 0;
		pw0[0] = pw1[0] = 1;
		for (int i = 1; i <= n; ++i) pw0[i] = pw0[i - 1] * c;
		for (int i = 1; i <= n; ++i) pw1[i] = pw1[i - 1] * (c - 1);
		for (int k = 1; k <= n; ++k) {
			Z val = calc(n - k, k);
			val *= pw0[k];
			val *= pw1[n - k];
			ans += val;
		}
		printf("%d\n", ans.x);
	}
	return 0;
}