Unique Paths in a Grid

You are given an n × n grid where each cell is either open (represented with .) or an obstacle (represented with #). Your task is to calculate the number of unique paths for a robot to move from the top-left corner (cell (1, 1)) to the bottom-right corner (cell (n, n)), by only moving either down or right. The answer should be given modulo \(10^9+7\).

Note: If the starting cell or the destination cell contains an obstacle, the answer is 0. Use dynamic programming to solve this problem efficiently.

inputFormat

The first line contains an integer n representing the size of the grid. The following n lines each contain a string of length n representing a row of the grid. Each character is either . (an open cell) or # (an obstacle).

outputFormat

Output a single integer denoting the number of unique paths from the top-left to the bottom-right cell modulo (10^9+7).## sample

3
...
.#.
...

2