Need help in mod 1000000007

Question

I am stuck in a problem in which I need to calculate something like:

((500!) / (20! X20! X20! X20! ...)) mod 1000000007

I understand how to calculate 500!% 1000000007, but I'm not sure how to distribute this operator in a section.

I'm currently trying to write code that overrides the denominators by its numerator based on its factors. But I'm not sure if this is a good approach to this.

I just need a mathematical way to solve such problems (mod1000000007), because they occur regularly in programming competitions and will help me prepare to encrypt Google code.

Answer 1

Method 1:

Think about how you usually calculate 500! / (20! * 20! * 20! * ...) 500! / (20! * 20! * 20! * ...) .

Do not multiply everything and do not divide at the end. Make your divisions in the middle. Then combine this with the module reduction from the previous question.

Method 2:

Prime factorize 500! and 20! . Then subtract the prime factors of 20! * 20! * 20! 20! * 20! * 20! (or how many of them you have) of 500! simple factors 500! .

Then rearrange the number by multiplying the remaining factors together. (at the same time taking the module along the path to keep the number from large)

Method 3:

If 1000000007 (or any module) is simple, you can do the division using the modular inverse .

Calculate 20! mod 1000000007 20! mod 1000000007 . Then calculate it with the modular inverse and multiply by 500! mod 1000000007 500! mod 1000000007 .