Distinct Paths in a Grid with Obstacles

You are given a grid with n rows and m columns. Each cell of the grid is either free (represented by .) or an obstacle (represented by #). Starting from the top-left cell, your task is to determine the number of distinct paths to reach the bottom-right cell. You can only move either to the right or downward.

If the starting or ending cell is an obstacle, or if there is no valid path, output 0.

The number of paths can be calculated using the recurrence relation given by $$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$ for any cell (i, j) that is free, with the starting condition defined as $$dp[0][0] = 1$$ if the top-left cell is free.

Input is provided via standard input (stdin) and output should be printed to standard output (stdout).

inputFormat

The first line of input contains two integers n and m separated by a space, where n is the number of rows and m is the number of columns in the grid.

This is followed by n lines, each containing a string of length m, representing the grid. Each character is either a . (free cell) or a # (obstacle).

outputFormat

Output a single integer — the number of distinct paths from the top-left corner to the bottom-right corner of the grid. If no such path exists, output 0.

3 3
...
...
...

6