simplyfying a mathematical expression

Question

How to calculate the value of below expression where $M$ is 1000000007 (prime) and $N$ can be any large number $\le 1000$?

\[\frac{N!}{(N/2)!(N/2)!} \mathbin{\%} M\]

It is possible to simplify it like \[\frac{(N/2 + 1)(N/2 + 2)\cdots N}{(N/2)!}\] but then $(N/2)!$ is still a huge number to calculate.

Now can also simply it further like (n/2 + 1)*(n/2 + 2)...*(n-1)/3*4...(n/2-1). But this still isn't enough.

Is it possible to break it down further?

Answer 1

What is needed here is Modular Multiplicative Inverse i.e. $x$ i sthe multiplicative inverse of a iff $$ax \equiv aa^{-1} \equiv 1 \mod m$$ The multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime, so if $m$ is prime then every number that is not a multiple of $m$ has a multiplicative inverse modulo $m$.

To solve the problem $ax \equiv 1 \mod m \implies ax-mk=1| k\in \mathbb Z$, since our problem satisfies Bézout's Identity ($a$ and $m$ are coprime.) one can apply Extended Euclidean Algorithm. You can find the algorithm in Python code here.

To compute $\cfrac {n!}{a!\times b!}$ modulo $m$, you can rewrite this as $n!\times(a!)^{-1}\times(b!)^{-1}$. As long as none of $a,\ b,\ $or $n$ is greater $m$, then there shouldn't be a problem at all.