Unique Paths in a Grid with Obstacles

You are given a grid with n rows and m columns. Each cell is either free (represented by '.') or contains an obstacle (represented by '#'). A robot starts at the top-left corner (cell (0, 0)) and needs to reach the bottom-right corner (cell (n-1, m-1)). The robot can only move either down or right at any point in time.

Your task is to compute the number of unique paths from the start to the destination. The answer should be computed modulo \(10^9+7\).

Note: If the starting cell or the destination cell is blocked, then no valid path exists. Use dynamic programming to solve the problem efficiently.

inputFormat

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

The following \(n\) lines each contain a string of length \(m\) consisting of characters '.' (free cell) and '#' (obstacle), representing the grid.

Input is given via stdin.

outputFormat

Output a single integer representing the number of unique paths from the top-left corner to the bottom-right corner modulo \(10^9+7\>.

Output should be written to stdout.

3 3
...
...
...

6