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.

-

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

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

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

n! = 6