Distinct Paths with Obstacles

You are given a grid of size M×N represented by a matrix where each cell is either free (0) or an obstacle (1). Your task is to compute the number of distinct paths from the top-left corner to the bottom-right corner, moving only right or down. If the starting or ending cell is an obstacle, then there is no valid path.

Since the answer can be very large, output your result modulo \(10^9+7\). A helpful hint is to use dynamic programming, where you can define a recurrence relation: \(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) (if the cell \((i,j)\) is not an obstacle).

inputFormat

The first line contains two integers, M and N, representing the number of rows and columns of the grid. Each of the following M lines contains N integers separated by spaces, where each integer is either 0 (free cell) or 1 (obstacle).

outputFormat

Output a single integer on a line, which is the number of distinct 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