Troyangles

Troy loves triangles. You have an N-by-N grid of . or # cells. Count the triangles formed only by # cells. A triangle of height h has h rows; row i contains 2i − 1 # characters centered on a vertical axis.

The first line contains N (1 ≤ N ≤ 2000). The next N lines contain the grid.

Print the number of triangles in the grid.