1

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?

Trevor Wilson
  • 16,989
g4ur4v
  • 169
  • Your question is ambiguous. The simplest way to calculate factorial is the way you stated above. This is obviously from an algorithm problem that tackles the overflow of the factorial function. But to attract good responses to your question, you need to explain what you want exactly. –  Feb 06 '13 at 20:44
  • this is actually in reference to quesion http://stackoverflow.com/questions/14736514/optimising-code-for-modular-arithmetic and this is an algorithm problem. – g4ur4v Feb 06 '13 at 20:47
  • 1
    could you include the reference in your question? –  Feb 06 '13 at 20:54

1 Answers1

2

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.