How can we compute N choose K modulus a prime number without overflow?

Question

How can we computer (N choose K)% M in C or C++ without invoking overflow ?

For the particular case when N (4<=N<=1000) and K (1<=K<=N) and M = 1000003.

Answer 1

To compute (n choose k) % M, you can separately compute the nominator (n!) modulus M and the denominator (k!*(n - k)!) modulus M and then multiply the nominator by the denominator's modular multiplicative inverse (in M). Since M is prime, you can use Fermat's Little Theorem to calculate the multiplicative inverse.

There is a nice explanation, with sample code, on the following link (problem SuperSum):

http://www.topcoder.com/wiki/display/tc/SRM+467

Answer 2

Since 1000000003 = 23 * 307 * 141623 you can calculate (n choses k) mod 23, 307 and 141623 and then apply the chinese reminder theorem[1]. When calculating n!, k! and (n-k)!, you should calculate everythinng mod 23, 307 and 141623 each step to prevent overflow.

In this way you should avoid overflow even in 32bit machines.

A little improvement would be to calculate (n choses k) mod 141623 and 7061 (23 * 307) (edit: but it can be a little tricky to calculate the inverse modulus 7061, so I wouldn't do this)

I'm sorry for my poor English.

[1]http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Edit2: Another potentially problem I've found is when calculating n! mod 23 (for example) it will probably be 0, but that doesn't implies that (n choses k) is 0 mod 23, so you should count how many times 23 divides n!, (n-k)! and k! before calculating (n choses k). Calculating this is easy, p divides n! exactly floor(n/p) + floor(n/p²) + ... times. If it happens that 23 divides n! the same times it divides k! and (n-k)!, the you proceed to calculate (n choses k) mod 23 dividing by 23 every multipler of it every time.The same applies for 307, but not for 141623