Google APAC TEST Dynamic programming

https://code.google.com/codejam/contest/4214486/dashboard#s=p0

I have seen few solutions and they are using following relation:
f(m, n) = (f(m - 1, n - 1) * m) % MOD + (f(m, n - 1) * (M - m)) % MOD

How to reach this equation?

1 Like

i think it is a variation of problem of finding the number of solution set of equation x1+x2+…+xr=n.
similar question was asked in TechFest2015,portal round
http://www.codechef.com/TCFS15P/problems/CANDIS.
how to approach such type of problems?