Calculating $\frac{\,^{n}P_{r}}{q!} \pmod{m}$

Question

For calculating the value of choosing $r$ items from $n$ items where $q$ are of same kind, and we should take modulo $m$, where $m$ is a prime; I used the following relation:

$$\frac{\,^{n}P_{r}}{q!} \pmod{m}$$

For calculating this

• I first calculated $n!$, then $n!\bmod{m}$

• Next, I calculated $(n-r)!$ and multiplied it with $q!$, i.e $t = q!(n-r)!$

• Then I multiplied the modular multiplicative inverse of $t$ with $n!$ and took the result modulo $m$ (i.e. $t^{-1}n!\bmod{m}$)

But I am not getting the correct answer.. E.g: if $n= 3$, $r = 2$, $q = 2$ then the expected result is $\frac{\,^{3}P_{2}}{2!}\equiv3\pmod{1000000007}$ but am getting $250000004$.. I can't understand my mistake here.. Thanks.

Answer 1

It's difficult to see what's going wrong here. How are you computing the multiplicative inverse of 2? Regardless of that, what value do you get for $2^{-1} \pmod{1000000007}$ ? (Since the modulus is odd, the answer should be immediately obvious.)