Unique Paths in Grid with Obstacles

You are given a grid of size \(n \times m\) where each cell is either empty (represented by 0) or contains an obstacle (represented by 1). Your task is to compute the number of unique paths from the top-left corner to the bottom-right corner of the grid. You can only move either down or right at any step.

If either the starting cell or the destination cell contains an obstacle, there are no valid paths. Since the answer can be very large, return the result modulo \(10^9+7\).

inputFormat

The first line of the input contains two integers (n) and (m) ((1 \leq n, m \leq 10^3)) representing the number of rows and columns respectively. The next (n) lines each contain (m) space-separated integers (each either 0 or 1), representing the grid. 0 indicates an empty cell and 1 indicates an obstacle.

outputFormat

Output a single integer — the number of unique paths from the top-left corner to the bottom-right corner, computed modulo (10^9+7).## sample

3 3
0 0 0
0 0 0
0 0 0

6