I want to calculate value of
F(N) = (F(N-1) * [((N-R+1)^(N-R+1))/(R^R)]) mod M for given values of N,R and M.
Here A^B shows A power B and NOT any Bitwise operation
Here M need not to be prime.How to approach this question?Please help because if M was prime that it would not have beed so difficult to find inverse of R^R mod M.
But as M can be any value ranging from 1 to 10^9.I am not able to tackle this problem.
N can be between 1 and 10^5 and R is less than or equal to N.
Assuming you know somehow that the result of the division is an integer:
As N and R are small, you can do this by computing the prime factorisation of N-R+1 and R.
If we know that R=p^a...q^b then R^R = p^(Ra)...q^(Rb).
Similarly you can work out the power of each prime in (N-R+1)^(N-R+1).
Subtract the powers of the primes in R^R from the powers of the primes in (N-R+1)^(N-R+1) gives you the powers of each prime in the result.
You can then use a standard binary exponentiation routine to compute the result modulo M with no inverses required.
