Unique Paths with Obstacles

Given an ( m \times n ) grid where each cell is either free (denoted by 0) or blocked by an obstacle (denoted by 1), your task is to determine the number of unique paths from the top-left corner to the bottom-right corner. You may only move either down or right at any point in time. If either the start cell or the end cell contains an obstacle, then no valid path exists. The final answer should be given modulo (10^9+7).

inputFormat

The first line of input contains two integers ( m ) and ( n ), representing the number of rows and columns respectively. This is followed by ( m ) lines, each containing ( n ) space-separated integers (0 or 1) representing the grid.

outputFormat

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

3 3
0 0 0
0 1 0
0 0 0

2