#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll qpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

const int N = 1e7 + 5;
ll fact[N], invf[N], f[N];

int main() {
    #ifdef _DEBUG
        freopen("data.txt", "r", stdin);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        ll n, c;
        cin >> n >> c;
        if (c == 1) {
            cout << "1\n";
            continue;
        }
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod, f[i] = 0;
        invf[n] = qpow(fact[n], mod - 2);
        for (int i = n - 1; i >= 0; i--) invf[i] = invf[i + 1] * (i + 1) % mod;
        f[0] = (2 - c + mod) % mod;
        ll now = c;
        ll top = 1;
        ll tmp = c * c % mod;
        ll mul = 1;
        for(int i = 0; i <= n; i++) {
            f[i] += now * top % mod * invf[i] % mod;
            top *= ((mod + 1) / 2 - i + mod) % mod;
            top %= mod;
            now = now * (mod + 4 - 4 * c % mod) % mod;
        }
        ll ans = 0;
        for (int i = 0; i <= n; i++) {
            ans = (ans + f[n - i] * mul % mod) % mod;
            mul = mul * tmp % mod;
        }
        cout << ans * qpow(2, mod - 2) % mod << "\n";
    }
}