Count Distinct Paths in a Grid

You are given an m x n grid represented as a binary matrix. Each cell in the grid is either empty (0) or blocked (1). Your task is to count the number of distinct paths from the top-left corner to the bottom-right corner. You can only move either right or down at any step.

If either the starting cell or the ending cell is blocked, then there is no valid path. Since the number of paths can be very large, you are required to output the result modulo \(10^9+7\).

Note: A path is defined as a sequence of moves from the top-left to the bottom-right following the rules above.

inputFormat

The first line contains two integers m and n representing the number of rows and columns of the grid respectively. This is followed by m lines each containing n space-separated integers (either 0 or 1) where 0 represents an empty cell and 1 represents a blocked cell.

outputFormat

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