Unique Paths with Obstacles

You are given an n x n grid where each cell is either empty or contains an obstacle. The grid is represented by characters: '.' for an empty cell and '#' for an obstacle. Your task is to compute the number of unique paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,n)), moving only right or down. You cannot pass through cells containing an obstacle. Since the answer can be very large, output it modulo \(10^9+7\).

Input Format: The first line contains an integer n indicating the size of the grid. This is followed by n lines, each containing a string of length n which represents a row of the grid.

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

inputFormat

The input is read from standard input. The first line contains an integer n (the size of the grid). Each of the next n lines contains a string of n characters ('.' for empty cells, '#' for obstacles).

outputFormat

A single integer on a line by itself representing the number of unique paths from the top-left to the bottom-right corner modulo (10^9+7).## sample

3
...
.#.
...

2