#include <vector> #include <list> #include <map> #include <set> #include <queue> #include <stack> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <limits> #include <cstring> #include <string> using namespace std; #define pairii pair<int, int> #define llong long long #define pb push_back #define sortall(x) sort((x).begin(), (x).end()) #define INFI numeric_limits<int>::max() #define INFLL numeric_limits<llong>::max() #define INFD numeric_limits<double>::max() #define FOR(i,s,n) for (int (i) = (s); (i) < (n); (i)++) #define FORZ(i,n) FOR((i),0,(n)) const llong MOD = 100003; inline llong refine(llong x) { while (x < 0) x += MOD; return x % MOD; } inline llong add(llong x, llong y) { return (refine(x) + refine(y)) % MOD; } inline llong sub(llong x, llong y) { return (refine(x) - refine(y) + MOD) % MOD; } inline llong mult(llong x, llong y) { return (refine(x) * refine(y)) % MOD; } // reference: http://stackoverflow.com/questions/10118137/fast-n-choose-k-mod-p-for-large-n long long invert_mod(long long k, long long m) { if (m == 0) return (k == 1 || k == -1) ? k : 0; if (m < 0) m = -m; k %= m; if (k < 0) k += m; int neg = 1; long long p1 = 1, p2 = 0, k1 = k, m1 = m, q, r, temp; while(k1 > 0) { q = m1 / k1; r = m1 % k1; temp = q*p1 + p2; p2 = p1; p1 = temp; m1 = k1; k1 = r; neg = !neg; } return neg ? m - p2 : p2; } long long choose_mod_two(long long n, long long k, long long p) { n %= p; if (n < k) return 0; if (k == 0 || k == n) return 1; if (k > n/2) k = n-k; long long num = n, den = 1; for(n = n-1; k > 1; --n, --k) { num = (num * n) % p; den = (den * k) % p; } den = invert_mod(den,p); return (num * den) % p; } long long choose_mod_one(long long n, long long k, long long p) { if (k < p) return choose_mod_two(n,k,p); long long q_n, r_n, q_k, r_k, choose; q_n = n / p; r_n = n % p; q_k = k / p; r_k = k % p; choose = choose_mod_two(r_n, r_k, p); choose *= choose_mod_one(q_n, q_k, p); return choose % p; } void solve() { llong n,k; cin >> n >> k; n -= k; llong x = n-k+1; if (x < 0) { cout << 0 << "\n"; return; } llong res = choose_mod_one(x+k, x, MOD); cout << res << "\n"; } int main() { #ifdef DEBUG freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t; scanf("%d",&t); FORZ(i,t) solve(); return 0; }