How to calculate nPr mod m, when m is a prime number?

Question

I need to find out the value of nPr%m.

This is the approach I used.

Find, n!%m, (n-r)!%m and divide them

However, for certain cases, (n-r)!%m is greater than n!%m, so the resultant nPr is 0.

What do I need to do then?

Answer 1

This is more a math question than a programming question, but anyway.

Note that

n! / (n - r)! = n * (n - 1) * ... * (n - r + 1)

Now for multiplication,

(a * b * c) % m = (((a * b) % m) * c) % m

i.e. rather than mod ming the entire product, you can mod m the intermediate result of any multiplication of two factors in the product.

I won't provide the full code here, but hopefully this will be enough for you to figure it out.