Distinct Paths in an n x n Grid

You are given an integer n and an n x n grid. Each cell in the grid is either . indicating a free cell or # indicating an obstacle. Your task is to count the number of distinct paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (n-1,n-1)) if you are only allowed to move either right or down at any point in time.

The dynamic programming recurrence used to solve the problem can be written in LaTeX as follows:

\( dp[i][j] = \begin{cases} 0 & \text{if } grid[i][j] = '#' \\ \left(dp[i-1][j] + dp[i][j-1]\right) & \text{otherwise} \end{cases} \)

Note that if the starting cell or the ending cell is blocked, the answer is 0. The grid is provided as n lines of characters, and you should output a single integer representing the number of distinct paths.

inputFormat

The first line of input contains an integer n, the size of the grid. Each of the following n lines contains a string of n characters where each character is either . (a free cell) or # (an obstacle).

outputFormat

Output a single integer which is the number of distinct paths from the top-left to the bottom-right corner of the grid.

## sample

3
...
.#.
...

2

</p>