ans = factorial(n) /factorial(r1) factorial(r2)…factorial(rk) where r1+r2+…+rk= n how to calculate this vale when n is large?

I want the ans mod 1000000007 value any suggestions will be appreciated

ans = factorial(n) /factorial(r1) factorial(r2)…factorial(rk) where r1+r2+…+rk= n how to calculate this vale when n is large?

I want the ans mod 1000000007 value any suggestions will be appreciated

Let us consider the general case for any such problem.

**ans= numerator/denominator.**

Let P be any prime number

So you have to calculate **ans%P**, given that you have numerator and denominator.

For such cases the answer comes out to be:

**ans= (numerator%P * power(denominator%P,P-2))%P.**

Now for your case you can easily calculate the numerator and denominator by pre-storing the factorial values, so all that is left is to calculate **(numerator/denominator)%P**.

**Note: To emphasize once again, this technique can be used only when P is a prime number.**

What I see is you have n as large than you could have a precomputation of combinations using Pascal triangle and modulus this with 1000000007 as the value may become large and than just multiply the combinations like ncr1* (n-r1)cr2*…*(n-(rk-2)c(rk-1)(mod) ans…

You could consider this question similar to it http://www.spoj.com/problems/GOODB/

ans= (numerator%P * power(denominator%P,P-2))%P.

can u xplain how dis equation comes… will b realy grateful