Maze Obstacle Problem Statement

Given an N * M grid representing a maze with obstacles, compute and return the total number of distinct paths from the top-left cell to the bottom-right cell. A cell in the maze is marked as -1 if it is blocked or a dead-end, otherwise, it is 0. You can only move right (i, j+1) or down (i+1, j) from any given cell. Since the result can be large, the number of paths should be returned modulo 10⁹ + 7.

Input:

The first line contains the integer 'T' representing the number of test cases.
Each test case consists of:
The first line with integers 'N' and 'M' denoting the dimensions of the maze.
The next N lines each contain M space-separated integers representing the maze grid.

Output:

For each test case, print a single integer indicating the number of valid paths modulo 109 + 7.
Output should be on a new line for each test case.

Example:

Input:
1
3 3
0 0 0
0 -1 0
0 0 0

Output:
2

Explanation:

There are two distinct paths from (0, 0) to (2, 2):

• (0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2)
• (0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2)

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 200
• Time Limit: 1 sec

Note:

You do not need to handle input/output; just implement the function to get the result.