Unique Paths in a Grid with Obstacles

You are given a grid of size R rows and C columns, where each cell is either free (represented by 0) or blocked by an obstacle (represented by 1). Your task is to calculate the number of unique paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (R,C)) moving only right or down. The answer should be computed modulo \(10^9 + 7\).

If the starting or ending cell has an obstacle, then the answer is 0.

Note: A path can only move down or right at any step.

inputFormat

The first line contains two integers, R and C, denoting the number of rows and columns of the grid, respectively.

This is followed by R lines, each containing C integers (either 0 or 1), specifying the grid. The cells with 1 are obstacles, and the cells with 0 are free cells.

The input is read from standard input (stdin).

outputFormat

Output a single integer – the number of unique paths from the top-left to the bottom-right corner, computed modulo \(10^9 + 7\). The output is printed to standard output (stdout).

3 3
0 0 0
0 1 0
0 0 0

2