ThreeLLogo

Please note that this problem has a non-standard time limit: 3 seconds.

A yet unknown "LLL Company" wants to design a logo. After a long discussion, company designers decided that the logo should consist of three letters L drawn in some way.

To start with something, designers drew N rows of M points each, one under another, so that these points form a rectangular grid. They also painted each point either white or black. Here is an example of what they could get for N = 4 and M = 5:



Designers agreed to draw each letter L as a union of a horizontal and a vertical line segment intersecting at their left and bottom ends, respectively. The segments must have positive lengths, and their endpoints must be white grid points. All grid points that lie on the segments must be white as well. For example, here are two valid placements of a letter:

 

Note that neither the letters nor the grid can be rotated.

The final requirement is that the three letters should be disjoint. That is, no white point should lie on two segments belonging to different letters.

You are given the grid with N rows and M columns, encoded as a String[] grid with N elements, each containing M characters. Each character is either '.' or '#', meaning that the corresponding point is either white or black, respectively.

Return the number of different possible logos with three L's drawn on them according to the requirements. Two logos are considered different if there is a pair of points that is connected by a line segment in exactly one of the logos.