Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  user31280 Feb 6 '13 at 20:44
    
this is actually in reference to quesion stackoverflow.com/questions/14736514/… and this is an algorithm problem. –  g4ur4v Feb 6 '13 at 20:47
1  
could you include the reference in your question? –  user31280 Feb 6 '13 at 20:54

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
1  
And if any of $a,b,n$ are greater than $m$, Lucas's theorem applies since $m$ is prime. –  Erick Wong Feb 7 '13 at 0:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.