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:
    
    
      
    **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 ≤ 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| < d. Rotated cross consists of balloons located in cells (x, y), such that |x - r| = |y - c| and |x - r| < 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.

Input

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.

Output

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.

Examples

Input

4
1233
0213
2020
0303


Output

108


Input

5
00300
00300
33333
00300
00300


Output

19683


Input

5
00003
02030
00300
03020
30000


Output

108


Input

5
21312
10003
10002
10003
23231


Output

3


Input

5
12131
12111
12112
21311
21212


Output

24

Note

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.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class VanyaBalloons {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 32768);
    static final double log2 = Math.log10(2), log3 = Math.log10(3), MOD = 1E9 + 7;

    //0-left; 1-top; 2-right; 3-bottom
    //4-diagonal esq top; 5-diagonal direita top; 6 -diagonal esq down; 7 - diagonal direita down;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(bf.readLine()), m[][] = new int[n+2][n+2], k[][][] = new int[n+2][n+2][8];
        double l[][][] = new double[n+2][n+2][8];
        int[] cx = {1, 1, n, n, 1, n, 1, n};
        int[] cy = {1, 1, n, n, 1, 1, n, n};
        int[] mx = {1, 1, -1, -1, 1, -1, 1, -1};
        int[] my = {1, 1, -1, -1, 1, 1, -1, -1};
        int[] dx = {-1, 0, 1, 0, -1, 1, -1, 1};
        int[] dy = {0, -1, 0, 1, -1, -1, 1, 1};

        for (int y = 1; y <= n; y++) {
            char[] line = bf.readLine().toCharArray();
            for (int x = 1; x <= n; x++)
                m[y][x] = line[x-1] - '0';
        }

        for(int dir = 0; dir < 8; dir++)
            for(int y = cy[dir]; y <= n && y > 0; y += my[dir])
                for(int x = cx[dir]; x <= n && x > 0; x += mx[dir]) {
                    int y2 = y + dy[dir], x2 = x + dx[dir];
                    if(m[y2][x2] != 0) {
                        k[y][x][dir] = k[y2][x2][dir] + 1;
                        l[y][x][dir] = l[y2][x2][dir] + getlog(m[y2][x2]);
                    }
                }

        double logans = Double.MIN_VALUE;
        int ra = 0, ya = 1, xa = 1;
        boolean weird = false;

        for(int y = 1; y <= n; y++)
            for(int x = 1; x <= n; x++)
                if(m[y][x] != 0){
                    for(int t = 0; t < 2; t++) {
                        //check normal cross
                        double log = getlog(m[y][x]);
                        int r = Math.min(Math.min(Math.min(k[y][x][t*4], k[y][x][t*4+1]), k[y][x][t*4+2]), k[y][x][t*4+3]);
                        for (int dir = t*4; dir < t*4+4; dir++)
                            log += l[y][x][dir] - l[y + dy[dir] * r][x + dx[dir] * r][dir];
                        if (log > logans) {
                            logans = log;
                            ya = y;
                            xa = x;
                            ra = r;
                            weird = t == 1;
                        }
                    }
                }


            double ans = m[ya][xa];
            if(!weird){
                for(int y = ya - ra; y <= ya + ra; y++)if(y != ya) ans = (ans * m[y][xa]) % MOD;
                for(int x = xa - ra; x <= xa + ra; x++)if(x != xa) ans = (ans * m[ya][x]) % MOD;
            }else{
                for(int y = ya - ra, x = xa - ra; y <= ya + ra && x <= xa + ra; y++, x++)if(y != ya || x != xa) ans = (ans * m[y][x]) % MOD;
                for(int y = ya + ra, x = xa - ra; y >= ya - ra && x <= xa + ra; y--, x++)if(y != ya || x != xa) ans = (ans * m[y][x]) % MOD;
            }
            System.out.println((long) ans);
    }

    public static double getlog(int i){
        if(i == 2) return log2;
        if (i == 3) return log3;
        if (i == 1) return 0.0;
        return -1;
    }
}
