I have often encountered problems(in gym) which reduce to finding C(n,r) % p , where p is **not necessarily prime** . Also n and r are both large . Essentialy they demand for the use of Lucas and Chinese Remainder Theorem.

For constraints let`s take this problem .

This link does help a lot but I am still confused , especially in the part which asks to use C.R.Theorem . How to apply CRT?

Also what if p is not a square free number ?

Along with explaination , a link to code would be extremely helpful.

Let

mandnbe coprime, , and . Thenx=ms+a=nt+bwheresandtare unknown. Rewrite this asms-nt=b-a. On the other hand, we can findkandlsuch thatmk+nl= 1, somk(b-a) +nl(b-a) =b-a. Subtracting the equalities, we get thatm(kb-ka-s) +n(lb-la+t) = 0, sokb-ka-sis divisible byn, andmk(b-a) -msis divisible bymn. So, .Okay thanks , i got the calculation part.

But what about my other question ?

what if p is not a square free number ?

You can have a look at this problem's editorial. https://www.hackerrank.com/challenges/ncr

This is implemented according to Granville's generalization of lucas theorem. Follow this link https://math.stackexchange.com/questions/95491/n-choose-k-bmod-m-using-chinese-remainder-theorem