Count Paths in a Grid with Obstacles

You are given a grid of size m × n where each cell is either open (denoted by 0) or blocked (denoted by 1). Starting at the top-left cell (0, 0) and moving to the bottom-right cell (m-1, n-1), your task is to compute the number of distinct paths available if you can only move either right or down at any step.

If the start or end cell is blocked, then no valid path exists. Since the total number of paths can be very large, output the answer modulo \(10^9+7\).

Input Format: The first line contains two integers m and n. This is followed by m lines, each containing n space-separated integers (0 or 1) describing the grid.

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

inputFormat

The input is read from stdin and is formatted as follows:

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

outputFormat

Output to stdout a single integer: the number of distinct 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