Number of Paths in a Grid

You are given a grid with N rows and M columns. Each cell in the grid is either free (denoted by '.') or contains an obstacle (denoted by '#'). Your task is to compute the number of distinct paths from the top-left cell (1, 1) to the bottom-right cell (N, M) if you can only move down or right.

Note: If the starting or ending cell is blocked, the answer is 0.

The recurrence relation used for dynamic programming is given by:

[ \text{dp}[i][j] = \begin{cases} 0, & \text{if } \text{grid}[i][j] = # \[6pt] \text{dp}[i-1][j] + \text{dp}[i][j-1], & \text{otherwise} \end{cases} ]

with the base condition \(\text{dp}[0][0] = 1\) provided that the starting cell is not blocked.

inputFormat

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

N M
row1
row2
...
rowN

Here, N and M are integers representing the number of rows and columns respectively. Each of the next N lines contains a string of length M representing a row of the grid.

outputFormat

Output a single integer representing the number of distinct paths from the top-left cell to the bottom-right cell, computed based on the dynamic programming relation.

## sample

3 3
...
.#.
...

2