Unique Paths in Grid with Obstacles

You are given an m x n grid where each cell contains either a 0 (empty cell) or a 1 (obstacle). A robot starts at the top-left corner of the grid and aims to reach the bottom-right corner. The robot can only move right or down at any step.

Your task is to compute the number of unique paths from the start to the destination, while avoiding obstacles. If either the starting cell or the destination cell contains an obstacle, the answer is 0. Since the number of paths may be very large, return the result modulo \(10^9+7\).

This problem can be efficiently solved using a dynamic programming approach.

inputFormat

The input is read from standard input (stdin). The first line contains two integers m and n representing the number of rows and columns. The next m lines each contain n space-separated integers (each either 0 or 1) representing the grid.

outputFormat

Output a single integer to standard output (stdout) — the number of unique paths from the top-left corner to the bottom-right corner modulo \(10^9+7\).

3 3
0 0 0
0 1 0
0 0 0

2