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.*;
import java.util.StringTokenizer;

public class Main {

    private static int[] dx = new int[]{0, 1, 1, 1};
    private static int[] dy = new int[]{1, 0, 1, -1};

    private static int n;
    private static int[][] a;

    private static int[][][][] count = new int[4][4][1000][1000];

    public static void main(String[] args) throws IOException {
        Reader in = new Reader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        n = in.nextInt();
//        n = 1000;
        a = new int[n][n];
        for (int i = 0; i < n; i++) {
            char[] s = in.next().toCharArray();
            for (int j = 0; j < n; j++) {
                a[i][j] = s[j] - '0';
//                a[i][j] = (i + j) % 4;
            }
        }

        int last = n - 1;
        for (int num = 0; num <= 3; num++) {
            if (num == 1) continue;
            for (int i = 0; i < n; i++) {
                int left = a[i][0] == num ? 1 : 0;
                int top = a[0][i] == num ? 1 : 0;
                count[0][num][i][0] = left;

                count[1][num][0][i] = top;

                count[2][num][i][0] = left;
                count[2][num][0][i] = top;

                count[3][num][0][i] = top;
                count[3][num][i][last] = a[i][last] == num ? 1 : 0;
            }
        }

        for (int i = 0; i < n; i++) {
            generateOneLine(0, i, 0);

            generateOneLine(1, 0, i);

            generateOneLine(2, i, 0);
            generateOneLine(2, 0, i);

            generateOneLine(3, 0, i);
            generateOneLine(3, i, last);
        }

        int[] ans = new int[]{-1, -1};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int level = 0; level < 2; level++) {
                    int left = 0;
                    int right = n;

                    while (left < right) {
                        int mid = (left + right + 1) >> 1;

                        int countZero = countAllSide(level, 0, i, j, mid);
                        if (countZero > 0) {
                            right = mid - 1;
                        } else {
                            left = mid;
                        }
                    }

                    if (a[i][j] != 0) {
                        int n2 = countAllSide(level, 2, i, j, left);
                        int n3 = countAllSide(level, 3, i, j, left);
                        if (isGreater(n2, n3, ans)) {
                            ans[0] = n2;
                            ans[1] = n3;
                        }
                    }
                }
            }
        }

        if (ans[0] == -1) {
            out.println(0);
        } else {
            long mod = 1000000007;
            out.println((powMod(2, ans[0], mod) * powMod(3, ans[1], mod)) % mod);
        }

        out.flush();
        in.close();
        out.close();
    }

    private static double log2 = Math.log(2);
    private static double log3 = Math.log(3);

    private static boolean isGreater(int n2, int n3, int[] b) {
        if (b[0] == -1) return true;

        int delta2 = n2 - b[0];
        int delta3 = n3 - b[1];

        if (delta2 >= 0 && delta3 >= 0) {
            return true;
        } else if (delta2 < 0 && delta3 < 0) {
            return false;
        } else if (delta2 >= 0) {
            return delta2 * log2 > -delta3 * log3;
        } else {
            return delta3 * log3 > -delta2 * log2;
        }
    }

    private static long powMod(long a, long b, long mod) {
        long ans = 1;
        while (b != 0) {
            if ((b & 1) != 0) {
                ans = (ans * a) % mod;
            }
            b >>= 1;
            a = (a * a) % mod;
        }
        return ans;
    }

    private static void generateOneLine(int level, int nowX, int nowY) {
        while (true) {
            int nextX = nowX + dx[level];
            int nextY = nowY + dy[level];
            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) break;

            for (int num = 0; num <= 3; num++) {
                count[level][num][nextX][nextY] = count[level][num][nowX][nowY] + (a[nextX][nextY] == num ? 1 : 0);
            }
            nowX = nextX;
            nowY = nextY;
        }
    }

    private static int countAllSide(int level, int num, int x, int y, int d) {
        return count(level * 2, num, x, y, -d) + count(level * 2, num, x, y, d) + count(level * 2 + 1, num, x, y, d) + count(level * 2 + 1, num, x, y, -d)
                - (a[x][y] == num ? 3 : 0);
    }

    private static int count(int level, int num, int x, int y, int d) {
        int nx = x + dx[level] * d;
        int ny = y + dy[level] * d;
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
            return n * n * 2;
        }
        int sum = Math.abs(count[level][num][nx][ny] - count[level][num][x][y]);
        int end = (d > 0 ? (a[x][y] == num ? 1 : 0) : (a[nx][ny] == num ? 1 : 0));
        return sum + end;
    }

    static class Reader {
        BufferedReader reader;
        StringTokenizer st;

        Reader(InputStreamReader stream) {
            reader = new BufferedReader(stream);
            st = null;
        }

        void close() throws IOException {
            reader.close();
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() throws IOException {
            return reader.readLine();
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

    }
}