#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; int a[MAXsqrtN][MAXN2]; int jc[MAXN]; inline int ksm(int a, int b) { //a ^ b int ans = 1; while (b) { if (b & 1) ans = (1ll * a * ans) % Mod; a = (1ll * a * a) % Mod; b >>= 1; } return ans; } inline int Inv(const int x) { return ksm(x, Mod - 2); } inline void rd(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(int x) { if (x > 9) w(x / 10); putchar(x % 10 + 48); } inline int C(const int& i, const 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; } int Block = 320; for (int i = 1; i * Block < MAXN; ++i) { int ii = i * Block, maxj = (ii + 1) / 2, x1 = 1, x2 = 1; for (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 (int j = 1, k = ii - 1; j <= maxj; ++j, --k) { a[i][j] = (1ll * a[i][j] + a[i][j - 1]) % Mod; } } int t, n, k, blocki, ii, ans; rd(t); cout << clock() << '\n'; int cnt = 0; while (t--) { rd(n), rd(k); ++n, ++k; blocki = n / Block, ii = blocki * Block; ans; 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; } w(ans), putchar(10); } return 0; }