Unique Maze Paths

You are given a grid maze with n rows and m columns. Each cell is either open (denoted by '.') or blocked (denoted by '#'). A mouse starts at the top-left corner and wants to reach the bottom-right corner. The mouse can only move either to the right or down at any step.

Formally, if we denote the cell in the i-th row and j-th column by \( cell(i, j) \), you need to count the number of unique paths from \( cell(0, 0) \) to \( cell(n-1, m-1) \) such that the mouse never enters a blocked cell. If either the starting cell or the destination cell is blocked, the answer is 0.

The number of paths can be determined using dynamic programming with the recurrence:

\[ dp[i][j] = \begin{cases} 0 & \text{if } grid[i][j] = '#' \\ (dp[i-1][j] + dp[i][j-1]) & \text{otherwise} \end{cases} \]

Your task is to compute and output the number of unique paths based on the given grid.

inputFormat

The first line of input contains two integers n and m - the number of rows and columns in the grid respectively. This is followed by n lines each containing a string of length m consisting of the characters '.' and '#' representing the grid.

Example:

3 3
.##
.#.
...

outputFormat

Output a single integer which is the number of unique paths from the top-left to the bottom-right corner of the maze. If no such path exists, output 0.

## sample

3 3
.##
.#.
...

1