# calculating (nPr/q!) % m

for calculating the value of choosing r items from n items where q are of same kind, and we should take %m , i used the following relation

• (nPr/q!) %m where m is prime

For calculating this

• i calculated n!

• n!%m

• then, i calculated (n-r)! and multiplied it with q!, i.e temp = (n-r)!*q!;

• Then i mulitplied modular mulitplicative inverse of temp with n! and took mod of result

but am not getting the correct answer..E.g if n= 3 ; r = 2; q = 2 then the expected result is (3P2/2!)%1000000007 = 3 but am getting 250000004 ..I can't understand my mistake here..Thanks.

-
Can you edit your question so the algorithm is shown step by step using a bullet list? –  Emil Vikström Jun 4 '12 at 16:39
modulo arithmetic doesn't work in division –  nims Jun 4 '12 at 16:40
@nims : so i've used multiplicative inverse –  pranay Jun 4 '12 at 16:44
@DanAndrews: thanks.. –  pranay Jun 4 '12 at 16:47

## migrated from stackoverflow.comJun 5 '12 at 21:03

This question came from our site for professional and enthusiast programmers.

The method you've described is correct, so there must be a bug in your implementation. In this case (n=3, r=2, q=2, m=1000000007):

n! = 6
temp = (n-r)!*q! = 2
Multiplicative inverse of 2 (mod m) = 500000004

result = (6*500000004) % 1000000007 = 3, the expected result.

-
thanks interjay..indeed there was a mistake in my implementation.. –  pranay Jun 4 '12 at 17:10