Count Paths in a Grid

You are given a grid of size N × M, where each cell is either free (denoted by .) or blocked (denoted by #). You start at the top-left cell and need to reach the bottom-right cell by only moving right or down. Your task is to count the number of different paths from the start to the destination, modulo \(10^9+7\).

The dynamic programming recurrence used is:

\[ \text{dp}[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#' \\[8pt] \left(\text{dp}[i-1][j] + \text{dp}[i][j-1]\right) \mod (10^9+7), & \text{if } grid[i][j] = '.' \end{cases} \]

with the base case \(\text{dp}[0][0]=1\) if the starting cell is free. Note that while the implementation uses 0-based indexing, the problem description uses 1-based cell positions.

inputFormat

The input is read from standard input and has the following format:

T
N M
row1
row2
...
rowN
... (repeated for each test case)

where:

• T is the number of test cases.
• For each test case, the first line contains two integers N and M representing the number of rows and columns.
• Each of the following N lines contains a string of length M that represents a row of the grid.

outputFormat

For each test case, output a single integer, which is the number of paths from the top-left to the bottom-right cell, modulo \(10^9+7\). Each answer should be printed on a new line.

## sample

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

2
0

</p>