Count Distinct Paths in a Grid

You are given a rectangular grid (court) with n rows and m columns. Each cell in the grid is either free (represented by a dot .) or blocked (represented by a hash #). The task is to count the number of distinct paths from the top-left corner to the bottom-right corner of the grid, where you can only move either to the right or downward.

If the starting cell or the ending cell is blocked, then there is no valid path. The answer should be computed using dynamic programming.

The mathematical recurrence is given by:

\[ \textit{dp}[i,j] = \begin{cases} 1 & \text{if } i = 0 \text{ and } j = 0, \\ 0 & \text{if } \text{cell } (i,j) \text{ is blocked}, \\ \textit{dp}[i-1,j] + \textit{dp}[i,j-1] & \text{otherwise.} \end{cases} \]

inputFormat

The input consists of multiple test cases. Each test case begins with a line containing two integers n and m (1 ≤ n, m ≤ 1000), representing the number of rows and columns, respectively. This is followed by n lines, each containing a string of length m that represents a row of the grid.

The input terminates with a line containing "0 0" which should not be processed.

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.

## sample

3 3
...
.#.
...
0 0

2

</p>