The Walk to School

Luka walks to school every day. The route is always the same and has three parts.

• First he walks exactly $\frac{1}{4}$ of the whole distance straight east.
• Then he walks $\frac{1}{2}$ of the whole distance straight south.
• Finally he walks the remaining $\frac{1}{4}$ straight east again.

Luka's village is an $N \times N$ grid of equally sized square cells. Some cells are packed with thorny bushes and cannot be entered at all, while the rest are grass and Luka can walk over them freely. While walking, Luka never walks along the border between two cells.

Luka's house is at the center of one grass cell, and the school is at the center of a different grass cell. Neither position is known. Every cell Luka passes through must be grass.

Write a program that counts the pairs of positions where Luka's house and the school can be.

In the picture below, grey cells cannot be entered and white cells can. The picture shows the answer to the first example, three pairs.

The first line contains the grid size $N$ ($1 \le N \le 2000$).

Each of the next $N$ lines contains $N$ characters. Every character is either '.' or the lowercase letter 'x'. A '.' is a grass cell and an 'x' is a cell that cannot be entered.

The grid is aligned with the compass. The cells in the first line are the northernmost, and the cells in the first column are the westernmost.

Print the number of pairs of positions where Luka's house and the school can be.