Lucas Theorem (nCr % p)

Time Complexity: O(n*r)
def ncrmodp(n,r,p):
# Optimized way
if(r>n-r):
r=n-r
ncr=[]
for i in range(n+1):
ncr.append([0])
ncr[i][0]=1
for i in range(1,n+1):
ncr[0].append(0)
for i in range(1,n+1):
for j in range(1,n+1):
ncr[i].append(0)
ncr[i][j]=(ncr[i-1][j]+ncr[i-1][j-1])
return(ncr[n][r]%p)


def ncrmodLucas(n,r,p):
if(r==0):
return 1
ni=n%p
ri=r%p
return (ncrmodLucas(n//p,r//p,p)*ncrmodp(ni,ri,p))%p



print(ncrmodLucas(1000,900,13))