#include <functional> #include <algorithm> #include <iostream> #include <climits> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cstring> #include <cassert> #include <cstdio> #include <string> #include <vector> #include <bitset> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <list> #include <set> #include <map> using namespace std; typedef long long LL; typedef pair<int, int> pii; typedef pair<int, pii> piii; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<piii> viii; #ifdef _WIN32 #define getchar_unlocked getchar #endif inline void inpint( int &n ) { n=0; register int ch = getchar_unlocked(); bool sign = 0; while(ch < 48 || ch > 57) { if(ch == '-') sign = 1; ch = getchar_unlocked(); } while(ch >= 48 && ch <= 57) { n = (n << 3) + (n << 1) + ch - 48, ch = getchar_unlocked(); } if(sign) n = -n; } inline int sqr(int x){return x * x;} inline int cube(int x){return x * x * x;} inline LL sqrLL(LL x){return x * x;} inline LL cubeLL(LL x){return x * x * x;} const LL LLINF = 9223372036854775807LL; const LL LLINF17 = 100000000000000000LL; const int INF = 2147483647; const int INF9 = 1000000000; const LL MOD = 100003; const double eps = 1e-7; const double PI = acos(-1.0); #define FOR(a,b,c) for (int (a)=(b); (a)<(c); (a)++) #define FORN(a,b,c) for (int (a)=(b); (a)<=(c); (a)++) #define FORD(a,b,c) for (int (a)=(b); (a)>=(c); (a)--) #define REP(i,n) FOR(i,0,n) #define REPN(i,n) FORN(i,1,n) #define REPD(i,n) FORD(i,n,1) #define RESET(a,b) memset(a,b,sizeof(a)) #define SYNC ios_base::sync_with_stdio(0); #define SIZE(a) (int)(a.size()) #define MIN(a,b) (a) = min((a),(b)) #define MAX(a,b) (a) = max((a),(b)) #define ALL(a) a.begin(),a.end() #define RALL(a) a.rbegin(),a.rend() #define SIZE(a) (int)(a.size()) #define LEN(a) (int)(a.length()) #define fi first #define se second #define pb push_back #define mp make_pair int dr[] = {1,0,-1,0,-1,1,1,-1}; int dc[] = {0,-1,0,1,1,1,-1,-1}; LL t, n, k; LL memo1[105][105][2]; inline LL dp(int pos, int rem, bool prev){ if(pos < 0 || rem < 0) return 0; if(pos == 0){ if(rem == 0) return 1; return 0; } LL &ret = memo1[pos][rem][prev]; if(ret != -1) return ret; ret = 0; ret += dp(pos - 1, rem, 0); ret %= MOD; if(!prev) ret += dp(pos - 1, rem - 1, 1); ret %= MOD; return ret; } LL arr1[MOD+5]; LL arr2[MOD+5]; LL memo[MOD + 5]; inline LL fastpow(LL b, LL p){ if(p == 1) return b; if(p&1) return (b * fastpow(b, p - 1)) % MOD; LL ret = fastpow(b, p>>1); return (ret * ret) % MOD; } inline LL nCr(LL a, LL b){ if(b > a) return 0; LL ret = 1; for(LL i = max(a - b, b) + 1; i <= a; i++){ ret *= i; ret %= MOD; } for(LL i = min(a - b, b); i >= 1; i--){ ret *= fastpow(i, MOD - 2); ret %= MOD; } return ret; } int main(){ RESET(memo,-1); RESET(memo1,-1); cin >> t; while(t--){ cin >> n >> k; // if(n <= 100 && k <= 100){ // printf("%lld\n",dp(n,k,0)); // continue; // } n = n - k + 1; if(n < k){ puts("0"); continue; } else if(n == k){ puts("1"); continue; } //calculate nCr(n - k + 1, k) LL tmpn = n, tmpk = k; int cnt1 = 0, cnt2 = 0; while(tmpn){ arr1[++cnt1] = tmpn % MOD; tmpn /= MOD; } while(tmpk){ arr2[++cnt2] = tmpk % MOD; tmpk /= MOD; } LL ans = 1; for(int i = 1; i <= min(cnt1, cnt2); i++){ ans *= nCr(arr1[i], arr2[i]); ans %= MOD; } cout << ans << endl; } return 0; }