lightoj 1067 - Combinations

Problem link

We know, nCr = n! / (r!*(n-r)! )

In this problem , we should output nCr % mod ... ( mod = 1e6+3 )
So, we should pre calculate factorial of i in fact[i], i<=1e6

But the problem is when we need to evaluate this expression (a/b)% mod
Because it is not similar to ( (a%mod)/(b%mod) ) % mod
Thus , to do this we may take help of modular multiplicative inverse.
I we know the  modular multiplicative inverse of b is x then the expression can be
evaluated as (a*x)%mod

In case you don't know about the modular multiplicative inverse, go here  😊

reference

A solution in c++