Counting ways of placing coins on a grid
===

the problem requires us to find out the number of ways of placing R coins on a N*M grid such that each row has at least one coin. Constraints given are N , M < 200 , R < N*M. I initially thought of backtracking, but i was made to realise that it would never finish in time . Can someone guide me to another solution? (DP , closed form formula.) any pointers would be nice. Thanks.