We all know the formula of nCr =n!/(r!*(n-r)!)

it’s a general formula,but this problem is about nCr %mod

it can be done with Modular multiplicative inverse

formula of nCr % mod is (f(n)%mod*(((r)^(mod-2))%mod*((n-r)^(mod-2))%mod)%mod;

here we need to calculate the result using bigmod function;

## View Code

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll dp[1000005];

const int mod = 1000003;

ll bigmod(ll a,ll b,ll mod)

{

if(b==0) return 1;

if(b&1)

{

return ((a%mod)*bigmod(a,b-1,mod))%mod;}

else{

ll x=bigmod(a,b/2,mod);

return (x%mod*x%mod)%mod;

}}

ll inverseEuler(ll a,ll b)

{

return bigmod(a,b-2,b);

}

int main()

{dp[0]=dp[1]=1;

for(ll i=2;i<=1000000;i++) dp[i]=((dp[i-1]*i)%mod); ll n,k; ll cs=1,t; cin>>t;

while(t–)

{cin>>n>>k;

ll res=((dp[n]%mod)*(inverseEuler(dp[k],mod)*inverseEuler(dp[n-k],mod))%mod)%mod;

printf(“Case %lld: %lld\n”,cs++,res);

}

}