Distinct Paths in a Grid

You are given an N x M grid where each cell is either open (denoted by 0) or blocked (denoted by 1). Your task is to calculate the number of distinct paths from the top-left corner to the bottom-right corner of the grid. You can only move either to the right or down at each step, and you cannot traverse blocked cells.

The answer should be computed modulo \(10^9+7\) (i.e. \(1000000007\)).

Hint: Use dynamic programming with the recurrence:

[ \textit{dp}[i][j] = \begin{cases} \textit{dp}[i-1][j] + \textit{dp}[i][j-1] & \text{if } grid[i][j] = 0, \ 0 & \text{if } grid[i][j] = 1. \end{cases} ]

inputFormat

The first line contains two integers N and M, representing the number of rows and columns in the grid, respectively.

This is followed by N lines, each containing M space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer which is the number of distinct paths from the top-left corner to the bottom-right corner, modulo \(1000000007\).

## sample

3 3
0 0 0
0 1 0
0 0 0

2

</p>