Paths To Reach :
Difficulty Level : Hard
Submissions : 167
Asked In :
Marks :100
: 1 | : 1
Given an N*M cross, matrix to find out no of possible ways to reach N, M cell from the cell 1,1 Given that some cells should not be visited in the grid the cell that is marked with 1 should not be visited all the cells that are marked with 0 are visitable cells. Find the total number of unique paths from (1,1) to (M,N)
If and is too large print ans
Input
The first line of input contains two integer N,M ($$$1 \le N,M \le 100 $$$).
The next N*M lines contain a matrix that contains 0 and 1.
Output
For each test case print the total number of unique paths.
Example
Input
3 3 0 0 0 0 1 0 0 0 0
Output
2
