Square#7757
Jian-Jia has a piece of metal material and wants to cut a square from it. The material is represented as an n \times n grid, and cuts can only be made along the grid boundaries.
Each cell of the grid is either usable or defective. Jian-Jia aims to cut the largest possible square that contains no defective cells. After determining the maximum possible size of such a square, he also wants to know how many different ways this square can be cut from the material.
Finally, Jian-Jia reports the product of the maximum size and the number of such possible ways.
Consider a 6 \times 6 material, as shown in the figure below. The black cells are defective. The largest square that can be cut has size 3 \times 3, and there are two possible ways to obtain it (shown as the red and green squares). Therefore, Jian-Jia reports the product 3 \cdot 2 = 6.
Your task is to determine the maximum size of a square that can be cut from the given material, as well as the number of distinct ways to obtain such a square. Output the product of these two values.
The first line contains one integer n~(1 \le n \le 1000) — the size of the material.
Each of the next lines contains integers. A value of indicates that the corresponding cell is usable, while indicates that it is defective.
Print one integer — the product of the size of the largest square without defective cells and the number of its possible positions in the material.
Example 1
Example 2