Need help in mod 1000000007 questions

Solution 1:

The key to these large-number modulus tasks is not to compute the full result before performing the modulus. You should reduce the modulus in the intermediate steps to keep the number small:

500! / 20! = 21 * 22 * 23 * ... * 500

21 * 22 * 23 * 24 * 25 * 26 * 27 = 4475671200

4475671200 mod 1000000007 = 475671172
475671172 * 28 mod 1000000007 = 318792725
318792725 * 29 mod 1000000007 = 244988962
244988962 * 30 mod 1000000007 = 349668811

...

 31768431 * 500 mod 1000000007 = 884215395

500! / 20! mod 1000000007 = 884215395

You don't need to reduce modulus at every single step. Just do it often enough to keep the number from getting too large.

Note that the max value of long is 2^63 - 1. So performing 64 bit multiplications between two positive integer values (i.e. one of the operands is a long) will not overflow long. You can safely perform the remainder operation % afterwards (if that is positive as well) and cast back to an integer when required.

Solution 2:

Start by observing that 500!/20! is the product of all numbers from 21 to 500, inclusive and Next, observe that you can perform modulo multiplication item by item, taking %1000000007 at the end of each operation. You should be able to write your program now. Be careful not to overflow the number: 32 bits may not be enough.

Solution 3:

I think this could be of some use for you

for(mod=prime,res=1,i=20;i<501;i++)
{
    res*=i; // an obvious step to be done 
    if(res>mod) // check if the number exceeds mod
    res%=mod; // so as to avoid the modulo as it is costly operation 
}