Method 1:
Think of how you would compute 500! / (20! * 20! * 20! * ...) normally.
Don’t multiply everything out and divide at the end. Do your divisions in the middle. Then combine this with the modulus reductions from your previous question.
Method 2:
Prime factorize 500! and 20!. Then subtract out the prime factors of 20! * 20! * 20! (or how ever many of them you have) from the prime factors of 500!.
Then rebuild the number by multiplying back the remaining factors together. (while taking modulus along the way to keep the number from getting large)
Method 3:
If 1000000007 (or whatever modulus) is prime, you can do divisions using the modular inverse.
Compute 20! mod 1000000007. Then compute it’s modular inverse and multiply it into 500! mod 1000000007.
2
solved Need help in mod 1000000007 [closed]