Distinct Paths in a Grid

You are given an n x m grid where each cell is either free (denoted by '.') or blocked (denoted by '#'). A robot starts at the top-left corner (cell (1,1)) and wants to reach the bottom-right corner (cell (n,m)). The robot can only move either right or down. Your task is to calculate the number of distinct paths the robot can take without stepping on a blocked cell. If either the start or the destination is blocked, then no valid path exists and the answer is 0.

Note: Use dynamic programming to solve the problem efficiently.

inputFormat

The first line contains two integers n and m separated by a space.

Each of the following n lines contains a string of m characters (without spaces) representing a row of the grid. Each character is either '.' (free cell) or '#' (blocked cell).

outputFormat

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

3 3
...
.#.
...

2