#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10000005;
const ll Ha = 1e9+7;

ll a[MAXN];
int jc[2*MAXN], ijc[2*MAXN];

ll ksm(ll x, ll k) {
    ll ret = 1;
    for (; k; k>>=1, x=x*x%Ha)
        if (k&1) ret = ret*x %Ha;
    return ret;
}

ll binom(ll x, ll y) {
    return 1ll*ijc[y] * ijc[x-y] %Ha * jc[x] %Ha;
}

ll inv(ll x) {
    if (x <= 1) return 1;
    return 1ll*ijc[x] * jc[x-1] %Ha;
}

void solve()
{
    ll n, c;
    ll tmp, tmp1, tmp2, A, B, iA;
    scanf("%lld%lld", &n, &c);

    if (n == 1) {
        puts("1");
        return;
    }

    if (c == 1) {
        printf("%lld\n", n);
        return;
    }

    tmp1 = 1ll*2*(c-1) %Ha *(c-2) %Ha;
    tmp2 = 1ll*2*c %Ha * (c-1) %Ha;
    for (int i=1; i<=n; i++) {
        tmp = 1ll*binom(2*i-1, i) * inv(2*i-1) %Ha * 2 %Ha * ksm(c-1, i);
        a[i] = 1ll*tmp2 * tmp %Ha;
        //a[i] = tmp;
    }
    a[0] = ((-tmp2 + tmp1)%Ha + Ha) %Ha;

    A = (4-4*c%Ha + Ha) %Ha;
    B = (1ll*4*c%Ha*c%Ha*(c-1)%Ha);
    iA = ksm(A, Ha-2);

    for (int i=0; i<=n; i++) {
        a[i] = (a[i]%Ha + Ha) %Ha;
        tmp = 1ll*a[i] * iA %Ha;
        a[i+1] -= 1ll*B * tmp %Ha;
        a[i] = tmp;
    }

    printf("%lld\n", a[n]);

}




int main()
{
    int ttt;
    scanf("%d", &ttt);

    jc[0] = 1;
    for (int i=1; i<2*MAXN; i++) jc[i] = 1ll*jc[i-1]*i %Ha;
    ijc[2*MAXN-1] = ksm(jc[2*MAXN-1], Ha-2);
    for (int i=2*MAXN-2; i>=0; i--) ijc[i] = 1ll*ijc[i+1] * (i+1) %Ha;

    while (ttt--) {
        solve();
    }
    return 0;
}