Unique Paths in Grid with Obstacles

Given a grid of dimensions (N \times M), where each cell is either free (denoted by 0) or blocked by an obstacle (denoted by 1), your task is to determine the number of distinct paths from the top-left corner to the bottom-right corner. You are only allowed to move either right or down at every step.

The problem can be solved using dynamic programming. Let (dp[i][j]) represent the number of ways to reach cell ((i,j)). The recurrence relation is given by: [ dp[i][j] = (dp[i-1][j] + dp[i][j-1]) \mod (10^9+7) ] with the base condition (dp[1][1]=1) if the starting cell is not blocked. If either the starting cell or the destination cell is blocked, the answer is 0.

Write a program that reads multiple test cases and outputs the number of distinct paths modulo (10^9+7) for each test case.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. For each test case, the first line contains two space-separated integers (N) and (M), representing the number of rows and columns of the grid respectively. This is followed by (N) lines, each containing (M) space-separated integers (either 0 or 1) representing the grid.

outputFormat

For each test case, output a single line containing the number of distinct paths from the top-left corner to the bottom-right corner of the grid, computed modulo (10^9+7).## sample

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

2