Counting Paths in a Grid

Given an n x m grid where each cell is either free ('.') or blocked ('#'), your task is to count the number of distinct paths from the top-left cell to the bottom-right cell. You can only move either down or right at any point in time, and you cannot pass through a blocked cell.

The recurrence relation used is given by \( dp[i,j] = dp[i-1,j] + dp[i,j-1] \) if the cell \( (i,j) \) is free, with the base case \( dp[0,0] = 1 \) when the starting cell is free. Your program should calculate the total number of distinct paths from the starting point to the destination.

inputFormat

The first line of the input contains two integers \( n \) and \( m \) representing the number of rows and columns respectively.

The next \( n \) lines each consist of a string of length \( m \) where each character is either '.' (representing a free cell) or '#' (representing an obstacle).

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner using only rightward or downward moves. If no such path exists, output 0.

3 3
...
.#.
...

2