Unique Paths in a Grid

You are given an (r \times c) grid where each cell is either passable ('.') or blocked ('#'). Your task is to compute the number of unique paths from the top-left corner (cell ((1,1))) to the bottom-right corner (cell ((r,c))). You can only move right or down at any step. A path is valid if it only passes through passable cells. Two paths are considered unique if the sequences of visited cells differ.

Input is read from standard input (stdin) and output must be written to standard output (stdout).

inputFormat

The first line of input contains two integers (r) and (c) representing the number of rows and columns of the grid respectively. The following (r) lines each contain a string of length (c) consisting of the characters '.' (passable) and '#' (blocked).

outputFormat

Output a single integer representing the number of unique paths from the top-left to the bottom-right corner of the grid. If the starting or ending cell is blocked, output 0.## sample

3 3
.##
..#
...

2