Counting Paths in a Grid

You are given an ( n \times m ) grid where each cell is either empty (represented by '.') or contains an obstacle (represented by '#'). Your task is to determine the number of distinct paths from the top-left cell to the bottom-right cell if you can only move either right or down. Note that both the starting cell and the ending cell must be accessible (i.e. '.'). If either is blocked, the answer is 0.

The recurrence relation for dynamic programming is given by:
( dp[i][j] = dp[i-1][j] + dp[i][j-1] ), if the cell ( (i, j) ) is accessible. Otherwise, ( dp[i][j] = 0 ).

inputFormat

The input is provided via standard input (stdin) and formatted as follows: The first line contains two integers ( n ) and ( m ) (with ( 1 \le n, m \le 1000 )) representing the number of rows and columns of the grid. Each of the next ( n ) lines contains a string of length ( m ) that describes one row of the grid. Each character is either '.' (an empty cell) or '#' (an obstacle).

outputFormat

Output a single integer to standard output (stdout): the number of distinct paths from the top-left cell to the bottom-right cell using only rightward or downward moves.## sample

3 3
...
.#.
...

2