A10416. Vanya and Balloons

Vanya plays a game of balloons on the field of size $n×n$ , where each cell contains a balloon with one of the values $0$ , $1$ , $2$ or $3$ . The goal is to destroy a cross, such that the product of all values of balloons in the cross is maximum possible. There are two types of crosses: normal and rotated. For example:

<br></br>**o**<br></br>**o**<br></br>ooooo<br></br>**o**<br></br>**o**<br></br>or

<br></br>o***o<br></br>*o*o*<br></br>**o**<br></br>*o*o*<br></br>o***o<br></br>Formally, the cross is given by three integers $r$ , $c$ and $d$ , such that $d<=r,c<=n-d+1$ . The normal cross consists of balloons located in cells $(x,y)$ (where $x$ stay for the number of the row and $y$ for the number of the column), such that $|x-r|·|y-c|=0$ and $|x-r|+|y-c|&lt;d$ . Rotated cross consists of balloons located in cells $(x,y)$ , such that $|x-r|=|y-c|$ and $|x-r|&lt;d$ .

Vanya wants to know the maximum possible product of the values of balls forming one cross. As this value can be large, output it modulo $10^{9}+7$ .

The first line of the input contains a single integer $n$ ( $1<=n<=1000$ ) — the number of rows and columns in the table with balloons.

The each of the following $n$ lines contains $n$ characters '0', '1', '2' or '3' — the description of the values in balloons.

Print the maximum possible product modulo $10^{9}+7$ . Note, that you are not asked to maximize the remainder modulo $10^{9}+7$ , but to find the maximum value and print it this modulo.

In the first sample, the maximum product is achieved for a rotated cross with a center in the cell $(3,3)$ and radius $1$ : $2·2·3·3·3=108$ .