#include <iostream> #include <cstdio> using namespace std; typedef long long i64; const int SIZE = 1e5+5; const int MOD = 1e9+7; int t, n[SIZE], k[SIZE]; i64 qpow(i64 a, i64 b) { i64 res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } namespace o1 { const int SIZE = 3005; int C[SIZE][SIZE]; int main() { for (int i = 0; i < SIZE; ++i) { C[i][0] = 1; for (int j = 1; j <= i; ++j) { C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD; } } for (int o = 1; o <= t; ++o) { i64 ans = 0; for (int i = 0; i <= k[o]; ++i) { ans = (ans + C[n[o]][i]) % MOD; } printf("%lld\n",ans); } return 0; } } namespace o2 { const int SIZE = 1e5+5; i64 fac[SIZE], inv[SIZE]; i64 C(i64 a, i64 b) { if (a == b || b == 0) return 1; return fac[a] * inv[b] % MOD * inv[a - b] % MOD; } i64 mem[SIZE]; int main() { fac[0] = 1; for (int i = 1; i < SIZE; ++i) { fac[i] = fac[i - 1] * i % MOD; inv[i] = qpow(fac[i], MOD - 2); } mem[0] = 1; for (int i = 1; i <= n[1]; ++i) mem[i] = (mem[i - 1] + C(n[1],i)) % MOD; for (int o = 1; o <= t; ++o) { printf("%lld\n",mem[k[o]]); } return 0; } } int main() { #ifdef fio freopen("test.in","r",stdin); #endif cin >> t; bool fg1 = true; bool fg2 = true; for (int i = 1; i <= t; ++i) { scanf("%d%d",n+i,k+i); if (n[i] > 3000 | k[i] > 3000) { fg1 = false; } if (n[i] != n[i-1]) { fg2 = false; } } if (fg1) { return o1::main(); } else if (fg2) { return o2::main(); } else { puts("!"); } return 0; }