Counting Distinct Shortest Paths in a Grid

You are given an \(N \times M\) grid where each cell is either free (denoted by '.') or blocked (denoted by '#'). You can only move right or down. Your task is to calculate the number of distinct shortest paths from the top-left corner (cell \( (1,1) \)) to the bottom-right corner (cell \( (N,M) \)).

If the starting cell or the destination cell is blocked, the answer is \(0\). In an obstacle-free grid the number of paths is given by the binomial coefficient \(\binom{N+M-2}{N-1}\), but obstacles may reduce this count. Use dynamic programming to solve the problem.

inputFormat

The first line contains two integers (N) and (M). The following (N) lines each contain a string of length (M) representing the grid. Each character is either '.' (free) or '#' (blocked).

outputFormat

Output a single integer representing the number of distinct shortest paths from the top-left corner to the bottom-right corner.## sample

3 3
...
.#.
...

2