Distinct Paths in a Grid

You are given an (N \times M) grid representing a map. Each cell of the grid is either open (denoted by '.') or blocked by an obstacle (denoted by '#'). Your task is to compute the number of distinct paths from the top-left corner to the bottom-right corner. You may only move either to the right or down at each step. Note that if the starting cell or the destination cell is blocked, then there is no valid path. This is a classical dynamic programming problem with a twist of obstacles.

inputFormat

The input is read from standard input (stdin). The first line of the input contains two integers (N) and (M) representing the number of rows and columns, respectively. Each of the following (N) lines contains a string of length (M) which represents a row of the grid. A character '.' stands for an open cell, and '#' stands for an obstacle.

outputFormat

Output a single integer to standard output (stdout) which is the number of distinct paths from the top-left corner to the bottom-right corner, following the movement restrictions. If there is no valid path, output 0.## sample

3 3
...
...
...

6