**PROBLEM LINK:**

**Setter** - K.S.K Vamsi

**Editorial** - K.S.K Vamsi

**DIFFICULTY** :

Medium

**PREREQUISITES** :

Permutations and Combinations, Basic Programming

**PROBLEM** :

Sam is trapped in a 2-D Matrix of size N by M. To escape he needs a key which is at position(i,j) in the matrix. He is at Top-leftmost Position and the door is at Bottom -rightmost position. He can only travel right or down. Find the no of ways in which he can escape from the matrix.

**EXPLANATION** :

The Problem can be broken down into two sub-problems one going from start to key and another starting from key all the way to end. So basically if we solve the problem from start to key we can similarly extend that from key to end. Go through this link to find the no of ways from start to key here. We can similarly

derive a formula from key to end. The final answer is the multiplication of two partial answers.

**SOLUTION** :

Setterâ€™s solution can be found here