Unique Paths with Obstacles

This problem asks you to compute the number of unique paths from the top-left corner to the bottom-right corner of an n × m grid. Each cell of the grid is either free (denoted by 0) or contains an obstacle (denoted by 1). You can move only right or down at any step. The result should be calculated modulo \(10^9+7\).

If the starting cell (top-left) or the ending cell (bottom-right) is an obstacle, then there is no valid path, and the answer should be 0.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\), denoting the number of rows and columns of the grid respectively. The following \(n\) lines each contain \(m\) space-separated integers (either 0 or 1) representing the grid where 0 indicates a free cell and 1 indicates an obstacle.

outputFormat

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

3 3
0 0 0
0 0 0
0 0 0

6