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.
#include <bits/stdc++.h>
using namespace std;
int n;
char buf[1005];
int a[2005][2005], b[2005][2005] = {};
int hor[4][2005][2005] = {}, ver[4][2005][2005];
pair<int, int> ans = make_pair(0, 0);
const long double RAT = log((long double)3) / log((long double)2);
const int MOD = 1e9 + 7;
pair<int, int> cmp(int a, int b, int c, int d) {
  if (a >= c && b >= d) return make_pair(a, b);
  if (a <= c && b <= d) return make_pair(c, d);
  if (a < c) {
    swap(a, c);
    swap(b, d);
  }
  if (RAT * (d - b) < a - c) return make_pair(a, b);
  return make_pair(c, d);
}
void solve() {
  for (int z = 0; z < (int)(4); ++z)
    if (z != 1)
      for (int i = 0; i < (int)(n); ++i)
        for (int j = 0; j < (int)(n); ++j) {
          hor[z][i][j + 1] = hor[z][i][j] + (a[i][j] == z);
          ver[z][i + 1][j] = ver[z][i][j] + (a[i][j] == z);
        }
  for (int i = 0; i < (int)(n); ++i)
    for (int j = 0; j < (int)(n); ++j)
      if (a[i][j] != 0 && a[i][j] != -1) {
        int lo = 0, mid, hi = min(min(i, n - 1 - i), min(j, n - 1 - j));
        while (lo < hi) {
          mid = (lo + hi + 1) >> 1;
          if (hor[0][i][j + mid + 1] - hor[0][i][j - mid] > 0 ||
              ver[0][i + mid + 1][j] - ver[0][i - mid][j] > 0) {
            hi = mid - 1;
          } else {
            lo = mid;
          }
        }
        int c = hor[2][i][j + lo + 1] - hor[2][i][j - lo] +
                ver[2][i + lo + 1][j] - ver[2][i - lo][j] - (a[i][j] == 2);
        int d = hor[3][i][j + lo + 1] - hor[3][i][j - lo] +
                ver[3][i + lo + 1][j] - ver[3][i - lo][j] - (a[i][j] == 3);
        ans = cmp(ans.first, ans.second, c, d);
      }
}
void rot() {
  memset(b, -1, sizeof b);
  int o = (n + 1) % 2;
  for (int i = 0; i < (int)(2 * n - 1); ++i)
    for (int j = 0; j < (int)(2 * n - 1); ++j)
      if (((i + j) & 1) == o) {
        b[i][j] = 0;
      }
  for (int i = 0; i < (int)(n); ++i)
    for (int j = 0; j < (int)(n); ++j) {
      b[n - 1 + i - j][i + j] = a[i][j];
    }
  memcpy(a, b, sizeof a);
  n = 2 * n - 1;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); ++i) {
    scanf("%s", buf);
    for (int j = 0; j < (int)(n); ++j) a[i][j] = buf[j] - '0';
  }
  bool ok = false;
  for (int i = 0; i < (int)(n); ++i)
    for (int j = 0; j < (int)(n); ++j)
      if (a[i][j]) ok = true;
  if (!ok) {
    printf("0\n");
    return 0;
  }
  solve();
  rot();
  solve();
  int res = 1;
  for (int i = 0; i < (int)(ans.first); ++i) res = 2ll * res % MOD;
  for (int i = 0; i < (int)(ans.second); ++i) res = 3ll * res % MOD;
  printf("%d\n", res);
  return 0;
}
