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.
//
//  javaGarden
//
//  Created by Van Thien on 6/3/16.
//  Copyright © 2016 Marclix. All rights reserved.
//

import java.util.*;
import java.io.*;
public class E677 {
	public static void main(String[] args) throws IOException{
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		if (System.getProperty("ONLINE_JUDGE") == null) {
			inputStream = new FileInputStream("input.inp");
//			outputStream = new FileOutputStream("output.out");
		} else {
			inputStream = System.in;
			outputStream = System.out;
		}
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(in, out);
		out.close();
	}
	
	static final int N = 1005;
	static final int oo = 1000000007;
	static final double pi = Math.acos(-1);
	
	
	static class Task {
		private int n = 0; 
		private int[][] a = new int[N][N];
		private int[][][] h = new int[N][N][4], v = new int[N][N][4], cc = new int[N][N][4], cp = new int[N][N][4];
		
		public void solve(InputReader in, PrintWriter out) {
			n = in.nextInt();
			ArrayList<prod> ar = new ArrayList<prod>();
			for(int i=1; i<=n; ++i) {
				String s = in.next();
				for(int j=1; j<=n; ++j) a[i][j] = s.charAt(j-1) - '0';
			}
//			for(int i=1; i<=n; ++i) {
//				for(int j=1; j<=n; ++j) out.print(a[i][j]);
//				out.println();
//			}
			prod max = new prod(-1, -1);
			for(int k=0; k<=3; ++k) count(k);
			for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) {
				int dmin = 1, dmax = Math.min(n+1-i, n+1-j);
				dmax = Math.min(dmax, Math.min(i, j));
				while (dmin <= dmax) {
					int dmid = (dmin+dmax)/2;
					if (check(dmid,i,j)) dmin = dmid+1; else dmax = dmid-1;
				}
				int dmid = (dmin+dmax)/2;
 				if (dmid == 0 || check(dmid, i,j) == false) ar.add(new prod(-1, -1)); else {
 					int cnt2 = h[i][j+dmid-1][2] - h[i][j-1][2] + h[i][j][2] - h[i][j-dmid][2] + v[i][j][2] - v[i-dmid][j][2] + v[i+dmid-1][j][2] - v[i-1][j][2];
 					int cnt3 = h[i][j+dmid-1][3] - h[i][j-1][3] + h[i][j][3] - h[i][j-dmid][3] + v[i][j][3] - v[i-dmid][j][3] + v[i+dmid-1][j][3] - v[i-1][j][3];
 					cnt2 -= (a[i][j] == 2 ? 1 : 0) * 3;
 					cnt3 -= (a[i][j] == 3 ? 1 : 0) * 3;
 					if (max.compareTo(new prod(cnt2, cnt3)) == -1) max = new prod(cnt2, cnt3);
 				}
			}
			for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) {
				int dmin = 1, dmax = Math.min(n+1-i, n+1-j);
				dmax = Math.min(dmax, Math.min(i, j));
				while (dmin <= dmax) {
					int dmid = (dmin+dmax)/2;
					if (check2(dmid,i,j)) dmin = dmid+1; else dmax = dmid-1;
				}
				int dmid = (dmin+dmax)/2;
 				if (dmid == 0 || check2(dmid, i,j) == false) ar.add(new prod(-1, -1)); else {
 					int cnt2 = cc[i+dmid-1][j+dmid-1][2] - cc[i-1][j-1][2] + cc[i][j][2] - cc[i-dmid][j-dmid][2] + cp[i][j][2] - cp[i-dmid][j+dmid][2] + cp[i+dmid-1][j-dmid+1][2] - cp[i-1][j+1][2];
 					int cnt3 = cc[i+dmid-1][j+dmid-1][3] - cc[i-1][j-1][3] + cc[i][j][3] - cc[i-dmid][j-dmid][3] + cp[i][j][3] - cp[i-dmid][j+dmid][3] + cp[i+dmid-1][j-dmid+1][3] - cp[i-1][j+1][3];
 					cnt2 -= (a[i][j] == 2 ? 1 : 0) * 3;
 					cnt3 -= (a[i][j] == 3 ? 1 : 0) * 3;
 					if (max.compareTo(new prod(cnt2, cnt3)) == -1) max = new prod(cnt2, cnt3);
 				}
			}
			long ans = (long)cal(2, max.two) * cal(3, max.three);
			out.println(ans % oo);
		}
		private void count(int k) {
			for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) {
				int temp = a[i][j] == k ? 1 : 0;
				h[i][j][k] = h[i][j-1][k] + temp;
				v[i][j][k] = v[i-1][j][k] + temp;
				cc[i][j][k] = cc[i-1][j-1][k] + temp;
				cp[i][j][k] = cp[i-1][j+1][k] + temp;
			}
		}
		private boolean check(int dmid, int i, int j) {
			if (h[i][j+dmid-1][0] - h[i][j-1][0] > 0) return false;
			if (h[i][j][0] - h[i][j-dmid][0] > 0) return false;
			if (v[i][j][0] - v[i-dmid][j][0] > 0) return false;
			if (v[i+dmid-1][j][0] - v[i-1][j][0] > 0) return false;
			return true;
		}
		private boolean check2(int dmid, int i, int j) {
			if (cc[i+dmid-1][j+dmid-1][0] - cc[i-1][j-1][0] > 0) return false;
			if (cc[i][j][0] - cc[i-dmid][j-dmid][0] > 0) return false;
			if (cp[i][j][0] - cp[i-dmid][j+dmid][0] > 0) return false;
			if (cp[i+dmid-1][j-dmid+1][0] - cp[i-1][j+1][0] > 0) return false;
			return true;
		}
		private long cal(int q, int k) {
			if (k < 0) return 0;
			long res = 1;
			for(int i=1; i<=k; ++i) {
				res *= q; res %= oo;
			}
			return res;
		}

	}
	static class prod implements Comparable<prod>{
		int two, three;
		prod(int two, int three) {this.two = two; this.three = three;}
		private double get(prod P) {
			return Math.log(2) * P.two + Math.log(3) * P.three;
		}
		public int compareTo(prod B) {
			if (B.two < 0) {
				if (two < 0) return 0;
				else return 1;
			}
			double aa = get(this);
			double bb = get(B);
			if (aa < bb) return -1;
			if (aa == bb) return 0;
			return 1;
		}
	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public char nextChar() {
			return next().charAt(0);
		}
	}
}
