#pragma GCC optimize("Ofast") #pragma GCC optimize("O3") #pragma GCC optimize("O2") #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 2, MAXN2 = 5e4 + 5, MAXsqrtN = 320, Mod = 1e9 + 7; unsigned int a[MAXsqrtN][MAXN2]; unsigned int jc[MAXN]; inline unsigned int ksm(unsigned int a, unsigned int b) { //a ^ b int ans = 1; for (; b; a = (1ll * a * a) % Mod, b >>= 1) { if (b & 1) ans = (1ll * a * ans) % Mod; } return ans; } int cnt; inline unsigned int Inv(const unsigned int x) { return ksm(x, Mod - 2); } inline void rd(unsigned int &s) { s = 0; int c(getchar()); while (c < 48 || c > 57) c = getchar(); while (c > 47 && c < 58) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar(); } inline void w(unsigned int x) { if (x > 9) w(x / 10); putchar(x % 10 + 48); } inline int C(const unsigned int& i, const unsigned int& j) { return (1ll * jc[i - 1] * Inv((1ll * jc[j - 1] * jc[i - j]) % Mod)) % Mod; } int main() { // freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); jc[0] = 1; for (int i = 1; i < MAXN; ++i) { jc[i] = (1ll * jc[i - 1] * i) % Mod; } unsigned int Block = 316; for (unsigned int i = 1; i * Block < MAXN; ++i) { unsigned int ii = i * Block, maxj = (ii + 1) / 2, x1 = 1, x2 = 1; for (unsigned int j = 1, k = ii - 1; j <= maxj; ++j, --k) { a[i][j] = (1ll * x1 * Inv(x2)) % Mod; x2 = (1ll * x2 * j) % Mod; x1 = (1ll * x1 * k) % Mod; } for (unsigned int j = 1, k = ii - 1; j <= maxj; ++j, --k) { a[i][j] = (1ll * a[i][j] + a[i][j - 1]) % Mod; } } unsigned int t, n, k, blocki, ii, ans, inv2 = Inv(2); rd(t); // cout << clock() << '\n'; // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); // cin >> t; while (t--) { rd(n), rd(k); // cin >> n >> k; ++n, ++k; blocki = n / Block, ii = blocki * Block; if (n - ii < ii + Block - n || ii + Block >= MAXN) { if (k > ii) { ans = ksm(2, k - 1); ii = k; } else if (k > (ii + 1) / 2) { ans = ((1ll * ksm(2, ii - 1) - a[blocki][ii - k]) % Mod + Mod) % Mod; } else { ans = a[blocki][k]; } for (int i = ii + 1; i <= n; ++i) { //s[n][k] ans = ((1ll * (ans << 1) - C(i - 1, k)) % Mod + Mod) % Mod; } } else { ++blocki; ii += Block; if (k > (ii + 1) / 2) { ans = ((1ll * ksm(2, ii - 1) - a[blocki][ii - k]) % Mod + Mod) % Mod; } else { ans = a[blocki][k]; } for (int i = ii - 1; i >= n; --i) { ans = (((1ll * ans + C(i, k)) % Mod) * inv2) % Mod; } } // cout << ans << '\n'; w(ans), putchar(10); } // cout <<'\n'<< clock() << '\n'; return 0; }