I’ve come across various problems where we need to present a solution modulus 1000000007 (M). Most of these problems involve calculating permutations and combinations involving big numbers. One such problem is MOVES The solution is presented here.
In this solution (and many others where we need to calculate permutations and combinations), a
factorial lookup table has been constructed. In addition to this, there’s another table which carries the lookup values of factorial of a number in denominator. e.g. for C(n,r) = n!/((n-r!)r!), two tables are used - fact and inverseFact. So C(n,r) is just a lookup == fact(n) x (inverseFact(n-r)%M) x (inverseFact(r)%M)
How is this inverseFact - (1/(N!)%M) lookup table constructed ? IT would be great in case any one can point me to the actual theory behind this.
