Unique Paths in a Grid with Obstacles

You are given a grid of size (m \times n) where each cell is either empty (denoted by 0) or blocked (denoted by 1). Your task is to compute the number of unique paths from the top-left corner to the bottom-right corner of the grid. You may only move either down or right at any point in time. If the starting or ending cell is blocked, no path exists. Since the number of paths can be very large, output the result modulo (10^9+7).

Example: Consider the grid:

3 3
0 0 0
0 1 0
0 0 0

The number of unique paths is 2.

inputFormat

Input is read from stdin. The first line contains two integers, (m) and (n), representing the number of rows and columns respectively. The following (m) lines each contain (n) space-separated integers (each either 0 or 1) representing the grid, where 0 indicates an empty cell and 1 indicates a blocked cell.

outputFormat

Output to stdout a single integer: 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