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

using namespace std;

const int maxn = 5e6;

int t, n, k;

const int p = 1e9 + 7;

int a[maxn + 1];
int b[maxn + 1];

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] * power(a[n - m] * a[m] % p, p - 2, p) % 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;
	}
	cin >> t;
	while (t--) {
		cin >> n >> k;
		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;
}

时间复杂度是 $O(\sum n\log n)$ 的，理论上不会 TLE，但是只有 20 分。