Unique Paths in Obstacle Grid

You are given a grid with r rows and c columns. Each cell in the grid is either 0 or 1, where 0 represents a free cell and 1 represents an obstacle. Your task is to compute the number of distinct paths from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (r-1, c-1)), moving only to the right or down, and avoiding obstacles.

Paths are computed modulo \(10^9+7\). Note that if either the starting cell or the destination cell is blocked (i.e. contains a 1), then no path exists and the answer is 0.

inputFormat

The first line contains two integers (r) and (c), representing the number of rows and columns respectively. Each of the following (r) lines contains (c) space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer: the number of distinct paths from the top-left to the bottom-right corner modulo (10^9+7).## sample

3 3
0 0 0
0 1 0
0 0 0

2