Unique Paths with Obstacles

You are given a grid of size (n \times m) represented by (n) strings, each of length (m). Each cell of the grid is either empty (denoted by a dot '.') or contains an obstacle (denoted by a hash '#'). Your task is to count the number of unique paths from the top-left corner (cell ((0, 0))) to the bottom-right corner (cell ((n-1, m-1))). At each step you are allowed to move either to the right or down. A path is valid only if it does not pass through any obstacles. If the starting cell or the destination cell contains an obstacle, the output should be (0).

The recurrence relation used in a dynamic programming solution is given by: [ dp[i][j] = dp[i-1][j] + dp[i][j-1] ] for cells that are not obstacles. Use this formula with appropriate boundary conditions to compute the result.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (m) ((1 \leq n, m \leq 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. Each character is either '.' (an empty cell) or '#' (an obstacle).

outputFormat

Output a single integer on standard output (stdout) which is the number of unique paths from the top-left corner to the bottom-right corner of the grid.## sample

3 3
...
...
...

6