Taco: Counting Distinct Paths in a Grid

You are given a grid with N rows and M columns. Each cell is either free (denoted by '.') or an obstacle (denoted by '#'). Your task is to calculate the total number of distinct paths from the top-left corner to the bottom-right corner while only moving right or down.

If the starting cell or the destination cell contains an obstacle, then there is no valid path.

The recurrence relation for the dynamic programming solution is given by: $$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$ (for cells not blocked by obstacles).

Implement a function that, given the grid dimensions and the grid itself, outputs the number of distinct paths from the top-left corner to the bottom-right corner.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two space-separated integers N and M (the number of rows and columns).
• The following N lines each contain a string of length M consisting of characters '.' and '#', representing the grid.

outputFormat

Output a single integer to stdout: the number of distinct paths from the top-left corner to the bottom-right corner.

3 3
...
...
...

6