Grid Path Counting

You are given a grid consisting of n rows and m columns. Each cell in the grid is either . (an empty cell) or # (a blocked cell). Starting from the top-left corner (1, 1), your task is to compute the number of ways to reach the bottom-right corner (n, m) if you can only move either to the right or downward.

The answer can be computed using the dynamic programming relation:

\[ dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#' \ (dp[i-1][j] + dp[i][j-1]), & \text{if } grid[i][j] = '.' \end{cases} \]

with the initial condition \(dp[0][0]=1\) if the starting cell is not blocked.

Input will be read from stdin and output should be printed to stdout.

inputFormat

The first line contains two integers n and m (the number of rows and columns respectively).

The following n lines each contain a string of length m consisting of characters . (empty cell) and # (blocked cell).

outputFormat

Output a single integer representing the number of ways to reach the bottom-right corner from the top-left corner, moving only right or down.

3 3
...
.#.
...

2