Given the definition of a function f as f(n)=1^1 * 2^2 * 3^3 * ... * (n-1)^(n-1) * n^n.
Another function g is defined as g(n,r)=f(n)/(f(r)*f(n-r))
Given an n,r,m we are to output g(n,r)%m where m is a large number.
What is the fastest way to solve this problem?
Constraints: 1<=n,r<=10^5 and 1<=m<=10^9
My approach: For g(5,2) and m = 24, effectively we need to calculate (4^4 *5^5)/(2^2) % 24
I tried to use fast exponentiation algorithm to find (4^4%24 * 5^5%24). Unfortunately there is a 2^2 in the denominator and fast exp doesn't seem to work here because (a/b)%c != (a%c/b%c)