A matrix of integers **A** of size **N x M** represents a grid consisting of **0** and **1**.

A robot is located at the top-left corner of this grid.

The robot can only move either down or right at any point in time.

The robot is trying to reach the bottom-right corner of the grid.

if **A[i][j] == 1** this represents a obstacle at position **(i, j)**. You cannot walk over obstacles and

cannot enter a cell containing obstacle.

if **A[i][j] == 0** this represents a empty at position **(i, j)**. You can free freely over empty cells and enter them.

Your task is to find how many unique paths are there from the top-left corner to the bottom right corner

if only down move or right move is allowed.

Since the number of paths can be very large your task is to find the number of unique paths modulo **(10 ^{9}+7)**.

**Input Format**

```
The only argument given is the matrix A.
```

**Output Format**

```
Return the number of unique paths modulo (10^9+7).
```

**Constraints**

```
1 <= N, M <= 500
0 <= A[i] <= 1
```

**For Example**

```
Input 1:
A = [ [0, 0, 0]
[0, 1, 0]
[0, 0, 0] ]
Output 1:
2
Explanation 1:
There are only two paths possible:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Input 2:
A : [ [0, 1]
[0, 0] ]
Output 2:
1
```

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

Sign Up

to access hints and editorial solutions for**Grid Unique Paths II**

to access hints and editorial solutions for

Loading...