Count Paths in a Grid

You are given a grid of size \(n \times m\) that consists of free cells represented by a '.' (dot) and blocked cells represented by a '#' (hash). Your task is to calculate 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 right or down at each step. A path cannot go through blocked cells.

Note: If the starting cell or the destination cell is blocked, then the number of paths is \(0\).

The answer should be computed using dynamic programming as follows:

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

Output the number of distinct paths.

inputFormat

The input is read from stdin in the following format:

n m
row1
row2
... 
rown

Where:

• n and m are integers representing the number of rows and columns respectively.
• Each of the next n lines contains a string of m characters (each character is either '.' or '#') without spaces, representing a row of the grid.

outputFormat

Output a single integer to stdout which is the number of distinct paths from the top-left corner to the bottom-right corner of the grid.

## sample

3 3
...
.#.
...

2