# Modular Division and Factorial

I am unfamiliar with number theory but am trying to calculate the following for a coding challenge:

$$\frac{(N-M-1)!}{N!(M-1)!}\pmod{Q}$$

where $Q$ is prime. I know that I can calculate the "modular" factorial fairly easily:

$$(N-M-1)!\bmod{Q} \equiv (((N-M-1)\times (N-M-2))\bmod{Q} \times \dots))\bmod{Q}$$

However, I'm not sure how I calculate the division part, I know that we can rewrite the fraction:

$$\frac{(N+M-1)!}{N!(M-1)!}\equiv (N+M-1)!\cdot (N!(M-1)!)^{-1}\pmod{Q}$$

However, can I compute the "modular" factorial of $N$ and $(M-1)$ in the same way and then compute the Modular Inverse of their product, or is there something else I need to do?

• Is $Q$ prime? $\,$ – Travis Feb 3 '15 at 12:59
• @Travis I've updated the question – Thomas Russell Feb 3 '15 at 13:00