Distinct Paths in a Grid

You are given an N × N grid where each cell is either . (an open cell) or # (an obstacle). You need to compute the number of distinct paths from the top-left corner to the bottom-right corner, moving only right or down. A path is valid only if it does not pass through any obstacles.

The recurrence relation used to count paths can be expressed in LaTeX as:

\(dp[i][j] = \begin{cases} 0 & \text{if } grid[i][j] = '#' \\ dp[i-1][j] + dp[i][j-1] & \text{otherwise, with appropriate boundary conditions} \end{cases}\)

If the starting cell or the destination cell is an obstacle, the answer is 0.

inputFormat

The input is given via stdin in the following format:

N
row_1
row_2
... 
row_N

Here, the first line contains an integer N representing the size of the grid. Each of the following N lines contains a string of length N composed of the characters . (open cell) and # (obstacle).

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner. The output should be printed to stdout.

## sample

4
....
....
....
....

20

</p>