Number of Shortest Paths in an Obstacle Grid

Problem Statement:

You are given a grid with N rows and M columns. Each cell in the grid is either free (denoted by '.') or blocked by an obstacle (denoted by '#'). Your task is to compute the number of distinct shortest paths from the top-left cell, (0, 0), to the bottom-right cell, $(N-1, M-1)$. You can only move in four directions: up, down, left, and right.

If the starting or the destination cell is blocked, or if no valid path exists, then the answer is 0.

Note: A shortest path is one where the number of moves is minimized. During the search for paths, if multiple routes lead to a cell in the same minimum number of steps, their path counts are accumulated.

Input and Output: The problem uses standard input and output. Read from stdin and output your result to stdout.

The length of a theoretical shortest path (if no obstacles were present) is N + M - 2, but obstacles may force a longer detour or make the destination unreachable.

inputFormat

The first line contains two integers, N and M, separated by a space, representing the number of rows and columns of the grid respectively.

The next N lines each contain a string of length M consisting of characters '.' and '#' representing the grid.

It is guaranteed that the input is provided via stdin.

outputFormat

Output a single integer representing the number of distinct shortest paths from the top-left to the bottom-right of the grid. This output should be written to stdout.

## sample

3 3
...
.#.
...

2

</p>