Unique Paths in a Grid with Obstacles

You are given a grid of size N x M where each cell is either open (0) or blocked (1). Your task is to find the number of unique paths from the top-left corner to the bottom-right corner moving only down or right, while avoiding the blocked cells.

If either the starting cell or the destination cell is blocked, then the number of unique paths is 0.

Since the answer can be very large, output the result modulo \(10^9+7\).

Note: The modulo is represented in LaTeX as \(10^9+7\).

inputFormat

The input is read from standard input (stdin) and consists of one or more test cases. The first line contains a single integer T, representing the number of test cases. For each test case, the first line contains two integers N and M indicating the dimensions of the grid. This is followed by N lines, each containing M space-separated integers representing the grid cells (0 for open cells and 1 for blocked cells).

T
N M
grid row 1
grid row 2
...
grid row N

outputFormat

For each test case, output a single line with an integer representing the number of unique paths from the top-left to the bottom-right cell modulo \(10^9+7\), written to standard output (stdout).

## sample

1
3 3
0 0 0
0 1 0
0 0 0

2

</p>