#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e7;

int t, n, k;

const int p = 1e9 + 7;

int a[maxn + 1];
int b[maxn + 1];
int s[maxn + 1];
int inv[maxn + 2];

int power(int base, int freq, int mod) {
    int ans = 1, tmp = base;
    while (freq) {
        if (freq & 1) ans = ans * tmp % mod;
        freq >>= 1;
        tmp = tmp * tmp % mod;
    }
    return ans;
}

int C(int n, int m) {
    return a[n] * inv[n - m] % p * inv[m] % p;
}

signed main() {
	a[0] = a[1] = 1;
	for (int i = 2; i <= maxn; ++i) {
		a[i] = a[i - 1] * i % p;
	}
	b[0] = 1;
	for (int i = 1; i <= maxn; ++i) {
		b[i] = (b[i - 1] << 1) % p;
	}
    inv[maxn] = power(a[maxn], p - 2, p);
    for (int i = maxn - 1; i >= 0; --i) {
        inv[i] = inv[i + 1] * (i + 1) % p;
    }
	cin >> t;
	while (t--) {
		cin >> n >> k;
        assert(n <= 5e6 && k <= 5e6);
		if (n == 1) {
			cout << k << endl;
			continue;
		}
		int tot = 0;
		if (k & 1) {
			for (int i = 1; i <= k >> 1; ++i) {
				tot += (C(k / 2, i) % p * b[i] % p * (C(n - 1, i - 1) % p + C(n - 2, i - 1) % p) % p) % p;
				tot %= p;
			}
		} else {
			for (int i = 1; i <= k >> 1; ++i) {
				tot += (C(k >> 1, i) % p * b[i] % p * C(n - 1, i - 1) % p) % p;
				tot %= p;
			}
		}
		
		cout << tot << endl;
	}
	return 0;
}