Counting Grid Paths Without Obstacles

You are given a square grid of size ( n \times n ) where each cell is either free (represented by a period '.') or blocked (represented by a hash sign '#'). Your task is to compute the number of distinct paths from the top-left cell to the bottom-right cell, moving only right or down, such that no path goes through a blocked cell. The answer must be given modulo (10^9+7).

Note: If either the start or the destination cell is blocked, the result is (0).

inputFormat

The first line contains an integer ( n ) representing the number of rows (and columns) of the grid. Each of the next ( n ) lines contains a string of length ( n ) consisting of the characters '.' (free cell) and '#' (blocked cell).

outputFormat

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

3
...
.#.
...

2