Path Counting in a Grid with Obstacles

You are given a grid with H rows and W columns. Each cell of the grid is either passable (denoted by '.') or blocked (denoted by '#'). A robot starts at the top-left cell and wants to reach the bottom-right cell by only moving right or down. Count the number of different paths that the robot can take to reach the destination, modulo \(10^9+7\). Note that if either the starting cell or the destination cell is blocked, there is no valid path.

Input Format: The first line contains two integers \(H\) and \(W\). The following \(H\) lines each contain a string of length \(W\) representing the grid.

Output Format: Output a single integer representing the number of possible paths modulo \(10^9+7\).

inputFormat

The input is given via standard input (stdin). The first line contains two space-separated integers \(H\) and \(W\). Each of the next \(H\) lines contains a string of length \(W\) consisting of the characters '.' and '#' only.

outputFormat

Output the number of ways you can reach from the top-left corner to the bottom-right corner of the grid modulo \(10^9+7\> on a single line from standard output (stdout).

3 3
...
.#.
...

2