The goal is to find \$f(n,r)\mod(m)\$ for the given values of \$n\$, \$r\$, \$m\$, where \$m\$ is a prime number.
$$f(n,r) = \dfrac{F(n)}{F(n-r) \cdot F(r)}$$
where
$$F(n) = 1^1 \cdot 2^2 \cdot 3^3 \cdot \ldots \cdot n^n$$
Here is the Python code snippet I've written:
n_r = n - r
num = 1
den = 1
if n_r > r:
for j in xrange(n_r + 1, n + 1):
num = num*(j**j)
for k in xrange(2, r + 1):
den = den*(k**k)
answer = num/den
ans = answer%m
print ans
else:
for j in xrange(r + 1, n + 1):
num = num*(j**j)
for k in xrange(2, n_r + 1):
den = den*(k**k)
answer = num/den
ans = answer%m
print ans
This code runs for small values of \$n\$ (when \$n <= 100\$). But for large values of \$n\$ ~ \$10^5\$, the code seems to be inefficient, exceeding the time limit of 2 sec. How can I generalize and optimize this computation?