InterviewBit Academy is now Scaler!
InterviewBit Academy is now Scaler Academy!

Grid Unique Paths II

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 (109+7).

Input Format

The only argument given is the matrix A.

Output Format

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


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

For Example

Input 1:
    A = [   [0, 0, 0]
            [0, 1, 0]
            [0, 0, 0] ]
Output 1:
    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:
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.
Start solving Grid Unique Paths II on Interview Code Editor
Sign Up
to access hints and editorial solutions for Grid Unique Paths II


Click here to start solving coding interview questions