Vanya plays a game of balloons on the field of size n \times 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:

**o**
**o**
ooooo
**o**
**o**

or

o***o
*o*o*
**o**
*o*o*
o***o

Formally, the cross is given by three integers r, c and d, such that d \le r,c \le 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| \cdot |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 109+7.

The first line of the input contains a single integer n (1 \le n \le 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 109+7. Note, that you are not asked to maximize the remainder modulo 109+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 \cdot 2 \cdot 3 \cdot 3 \cdot 3=108.