Distinct Paths in a Grid with Obstacles

You are given a grid of size \(m \times n\) consisting of two types of cells: an empty cell represented by . and a blocked cell represented by #. A robot starts at the top-left corner (cell (1,1)) and aims to reach the bottom-right corner (cell (m,n)). The robot can only move either right or down at any step and cannot enter any blocked cell.

Your task is to count the number of distinct paths from the top-left corner to the bottom-right corner. If either the starting cell or the destination cell is blocked, the answer is 0.

Note: There is no requirement to take the answer modulo any number. Use dynamic programming to compute the number of unique paths.

inputFormat

The input is given via standard input (stdin). The first line contains two integers (m) and (n) representing the number of rows and columns of the grid. The following (m) lines each contain a string of length (n) consisting only of the characters . and #, which describe the grid.

outputFormat

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

3 3
...
.#.
...

2