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

 */
public class Main
{
	public static void main(String[] arg) throws IOException
	{
		new Main();
	}
	long MOD = 1_000_000_007;
	double oo = -100000;
	int n;
	long[][] g;
	double[][] log;
	double[][][] d;
	int[][][] r;
	public Main() throws IOException
	{
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		n = in.nextInt();
		g = new long[n][n];
		log = new double[n][n];
		for(int i = 0; i < n; i++)
		{
			String s = in.next();
			for(int j = 0; j < n; j++)
			{
				g[i][j] = s.charAt(j)-'0';
				if(g[i][j] != 0) log[i][j] = Math.log(g[i][j]);
			}
		}
		d = new double[8][n][n];
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				for(int k = 0; k < 8; k++)
				{
					d[k][i][j] = log[i][j];
				}
			}
		}
		r = new int[8][n][n];
		int[] di = {0, -1, -1, -1, 0, 1, 1, 1};
		int[] dj = {-1, -1, 0, 1, 1, 1, 0, -1};
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(g[n-i-1][n-j-1] != 0)
				{
					r[4][n-i-1][n-j-1]++;
					r[6][n-i-1][n-j-1]++;
					r[5][n-i-1][n-j-1]++;
					if(in_bound(n-i-1+di[4], n-j-1+dj[4]))
					{
						r[4][n-i-1][n-j-1] += r[4][n-i-1+di[4]][n-j-1+dj[4]];
						d[4][n-i-1][n-j-1] += d[4][n-i-1+di[4]][n-j-1+dj[4]];
					}
					if(in_bound(n-i-1+di[6], n-j-1+dj[6]))
					{
						r[6][n-i-1][n-j-1] += r[6][n-i-1+di[6]][n-j-1+dj[6]];
						d[6][n-i-1][n-j-1] += d[6][n-i-1+di[6]][n-j-1+dj[6]];
					}
					if(in_bound(n-i-1+di[5], n-j-1+dj[5]))
					{
						r[5][n-i-1][n-j-1] += r[5][n-i-1+di[5]][n-j-1+dj[5]];
						d[5][n-i-1][n-j-1] += d[5][n-i-1+di[5]][n-j-1+dj[5]];
					}
				}
				if(g[i][n-j-1] != 0)
				{
					r[3][i][n-j-1]++;
					if(in_bound(i+di[3], n-j-1+dj[3]))
					{
						r[3][i][n-j-1] += r[3][i+di[3]][n-j-1+dj[3]];
						d[3][i][n-j-1] += d[3][i+di[3]][n-j-1+dj[3]];
					}
				}
				if(g[n-i-1][j] != 0)
				{
					r[7][n-i-1][j]++;
					if(in_bound(n-i-1+di[7], j+dj[7]))
					{
						r[7][n-i-1][j] += r[7][n-i-1+di[7]][j+dj[7]];
						d[7][n-i-1][j] += d[7][n-i-1+di[7]][j+dj[7]];
					}
				}
				if(g[i][j] != 0)
				{
					r[0][i][j]++;
					r[2][i][j]++;
					if(in_bound(i+di[0], j+dj[0]))
					{
						r[0][i][j] += r[0][i+di[0]][j+dj[0]];
						d[0][i][j] += d[0][i+di[0]][j+dj[0]];
					}
					if(in_bound(i+di[2], j+dj[2]))
					{
						r[2][i][j] += r[2][i+di[2]][j+dj[2]];
						d[2][i][j] += d[2][i+di[2]][j+dj[2]];
					}
					
					r[1][i][j]++;
					if(in_bound(i+di[1], j+dj[1]))
					{
						r[1][i][j] += r[1][i+di[1]][j+dj[1]];
						d[1][i][j] += d[1][i+di[1]][j+dj[1]];
					}

				}
			}
		}
//		for(int i = 0; i < n; i++)
//		{
//			for(int j = 0; j < n; j++)
//			{
//				System.out.printf("%.2f ", d[7][i][j]);
//			}
//			System.out.println();
//		}
//		System.out.println();
		int bi = 0;
		int bj = 0;
		double best = 0;
		boolean f = true;
		int br = 1;
//		System.out.println("2: "+Math.log(2));
//		System.out.println("3: "+Math.log(3));
//		System.out.println(3*Math.log(2)+Math.log(3));
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(g[i][j] == 0) continue;
				int[] rad = new int[2]; Arrays.fill(rad, Integer.MAX_VALUE);
				for(int k = 0; k < 8; k++)
				{
					rad[k%2] = Math.min(rad[k%2], r[k][i][j]);
				}
//				if(i == 2 && j == 2) System.out.println(Arrays.toString(rad));
				double[] sum = new double[2];
				for(int k = 0; k < 8; k ++)
				{
					double val = d[k][i][j];
					if(in_bound(i+rad[k%2]*di[k], j+rad[k%2]*dj[k])) val -= d[k][i+rad[k%2]*di[k]][j+rad[k%2]*dj[k]];
					sum[k%2] += val;
//					if(i == 3 && j == 2) System.out.println(Arrays.toString(sum));
				}
				for(int k = 0; k < 2; k++)
				{
					sum[k] -= 3*log[i][j];
				}
//				if(i == 3 && j == 2) System.out.println(best + " " + Arrays.toString(sum));
				for(int k = 0; k < 2; k++)
				{
					if(sum[k] > best)
					{
						best = sum[k];
						bi = i;
						bj = j;
						br = rad[k];
						if(k == 0) f = true;
						else f = false;
					}
				}
				
			}
		}
//		System.out.println(bi + " " + bj + " " + br + " " + f + " " + best);
		long ret = 1;
		for(int i = 0; i < br; i++)
		{
			if(f)
			{
				if(i == 0)
				{
					ret *= g[bi][bj];
				}
				else
				{
					for(int j = 0; j < 8; j+=2)
					{
						ret *= g[bi+i*di[j]][bj+i*dj[j]];
						ret %= MOD;
					}
				}
			}
			else
			{
				if(i == 0)
				{
					ret *= g[bi][bj];
				}
				else
				{
					for(int j = 1; j < 8; j+=2)
					{
						ret *= g[bi+i*di[j]][bj+i*dj[j]];
						ret %= MOD;
					}
				}
			}
		}
		
		out.println(ret);
		in.close(); out.close();
	}
	boolean in_bound(int i, int j)
	{
		return 0 <= i && i < n && 0 <= j && j < n;
	}
	class Pair implements Comparable<Pair>
	{
		int d, r, c, key;
		public Pair(int a, int b, int c, int d)
		{
			this.d = a;
			r = b;
			this.c = c;
			key = d;
		}
		public int compareTo(Pair p)
		{
			return d-p.d;
		}
		public String toString()
		{
			return d + " " + r + " " + c + " " + key;
		}
	}
	class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		public FastScanner(InputStream in)
		{
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}
		public String next() throws IOException
		{
			while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
		public void close() throws IOException
		{
			br.close();
		}
	}
}
