Unique Paths with Obstacles

You are given a grid of size M x N where some cells are obstacles. A cell with an obstacle is denoted by -1 and a free cell by 0. Starting from the top-left cell and moving only right or down, your task is to determine the number of unique paths to reach the bottom-right cell.

If the start or destination cell is an obstacle, then it is impossible to reach the destination, and the answer should be 0.

Using dynamic programming, you can define the recurrence for a cell that is not blocked as follows:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)

Remember that the answer should be given modulo \(10^9+7\).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers \(M\) and \(N\), representing the number of rows and columns of the grid.
• The next \(M\) lines each contain \(N\) space-separated integers. Each integer is either 0 (a free cell) or -1 (an obstacle).

outputFormat

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

## sample

3 3
0 0 0
0 -1 0
0 0 0

2

</p>