Distinct Grid Paths with Obstacles

In this problem, you are given a grid of size (N \times M) where each cell is either an empty cell denoted by a dot ('.') or an obstacle denoted by a hash ('#'). Your task is to compute the number of distinct paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (N,M)) while only moving either down or right. A cell containing an obstacle cannot be part of a valid path. Since the number of paths can be very large, report your answer modulo (10^9+7).

The dynamic programming recurrence for computing the number of ways is given by: [ dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#' \ (dp[i-1][j] + dp[i][j-1]) \bmod (10^9+7), & \text{otherwise} \end{cases} ] with the base condition (dp[0][0]=1) if the top-left cell is not blocked.

This problem may have multiple test cases. Read each test case, compute the number of valid paths for the given grid, and print the result on a new line.

inputFormat

Input is read from standard input (stdin). The first line contains a single integer (T) denoting the number of test cases. For each test case, the first line contains two integers (N) and (M) that represent the number of rows and columns of the grid. The next (N) lines each contain a string of length (M), representing the grid, where each character is either '.' or '#'.

outputFormat

For each test case, output the number of distinct paths from the top-left to the bottom-right cell, modulo (10^9+7). Each answer should be printed on a separate line to standard output (stdout).## sample

2
3 3
...
.#.
...
2 2
##
.#

2
0