#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int>PII; const double eps=1e-5; const double pi=acos(-1.0); //const int mod=1e9+7; const int INF=0x3f3f3f3f; /* 题意: 求一个组合数,但是要取膜,所以我们要逆元; 思路: 利用费法小定理,就可以啦; */ //快速幂; const LL mod=1000003; const int N=1e6+10; LL f[N]; LL cal(LL g,LL x) { LL ans=1; while(g) { if(g&1) ans=ans*x%mod; x=x*x%mod; g>>=1; } return ans; } //C(N,M)=N!/(M!*(N-M)!); //这里要取膜,所以要逆元(除法不适用于取膜); //这里因为mod是质数,所以利用费马小定理就好了/// void solve(LL n,LL m) { printf("%lld ",f[n]*cal(mod-2,f[n-m])%mod*cal(mod-2,f[m])%mod); } //预处理一个阶乘数组; void init() { f[0]=1; for(LL i=1;i<=1000000;i++) f[i]=f[i-1]*i%mod; } int main() { init(); int T,cas=1; scanf("%d",&T); while(T--) { LL n,k; scanf("%lld%lld",&n,&k); printf("Case %d: ",cas++); solve(n,k); } return 0; }