#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define fi first
#define se second
#define For(x, y, z) for(int x = (y); x <= (z); x++)
#define Rep(x, y, z) for(int x = (y); x >= (z); x--)
using namespace std;
const int Mod = 1e9 + 7, MAXN = 1e7 + 5;
char buf[1 << 12], *pp1 = buf, *pp2 = buf, nc;
inline char gc() {
    return (pp1 == pp2) && (pp2 = (pp1 = buf) + fread(buf, 1, 1 << 12, stdin), pp1 == pp2) ? EOF : *pp1++;
}
inline int read() {
    int x = 0, ny = 1;
    for(; nc = gc(), (nc < 48 || nc > 57) && nc != EOF; ) 
        if(nc == '-') ny = -1;
    if(nc < 0) return nc;
    x = nc ^ 48;
    for(; nc = gc(), (nc >= 48 && nc <= 57 && nc != EOF); )
        x = (x << 3) + (x << 1) + (nc ^ 48);
    return x * ny;
}
int a[MAXN], Inv[MAXN];
inline void Init() {
    Inv[1] = 1;
    For(i, 2, 1e7) Inv[i] = 1ll * Inv[Mod % i] * (Mod - Mod / i) % Mod;
}
int n, c;
inline void Solve() {
    n = read(), c = read();
    int t = 4ll * (c - 1) % Mod, now = Mod + 1 >> 1, res = 0;
    a[0] = c;
    For(i, 1, n) a[i] =  1ll * a[i - 1] * now % Mod * Inv[i] % Mod * (Mod - t) % Mod, now--;   
    a[0] = (a[0] - c + 2 + Mod) % Mod, now = 1;
    For(i, 0, n) res = (res + 1ll * now * a[n - i]) % Mod, now = 1ll * now * c % Mod * c % Mod;
    res = 1ll * res * (Mod + 1 >> 1) % Mod;
    cout << res << '\n';
}
int main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    Init();
    for(int t = read(); t--; ) Solve();
    return 0;
}