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;
const double PI = 4 * atan(1);
const double PI2 = PI * 2;
int n, m, tot, ans, cnt;
typedef struct sege {
  int a;
  int nxt;
  friend int operator<(struct sege x, struct sege y) { return x.nxt > y.nxt; }
} E, *Ptr;
typedef struct mat {
  int m[10][10];
  int n;
  friend struct mat operator*(struct mat x, struct mat y) {
    struct mat r;
    r.n = x.n;
    for (int i = 0; i < r.n; ++i)
      for (int j = 0; j < r.n; ++j) {
        r.m[i][j] = 0;
        for (int k = 0; k < r.n; ++k) r.m[i][j] += x.m[i][k] * y.m[k][j];
      }
    return r;
  }
} MA;
long long qpow(int x, long long y, int p) {
  long long res = 1, b = x;
  while (y) {
    if (y & 1) res = res * b % p;
    b = b * b % p;
    y >>= 1;
  }
  return res;
}
void extgcd(int a, int b, int &x, int &y) {
  if (b != 0) {
    extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
}
int mod_inv(int a, int p) {
  int x, y;
  extgcd(a, p, x, y);
  return (p + x % p) % p;
}
int invm(int x, int p) {
  x %= p;
  if (x == 0)
    return 0;
  else
    return mod_inv(x, p);
}
int crt(int x, int m1, int y, int m2) {
  if (y > x)
    return ((y - x) % m2 * invm(m1, m2) % m2 * m1 % m2 + x) % m2;
  else
    return ((x - y) % m1 * invm(m2, m1) % m1 * m2 % m1 + y) % m1;
}
const int p = 1000000007;
long long getc(int n, int m) {
  if (n < m) return 0;
  if (m > n - m) m = n - m;
  long long s1 = 1, s2 = 1;
  for (int i = 0; i < m; i++) {
    s1 = s1 * (n - i) % p;
    s2 = s2 * (i + 1) % p;
  }
  return s1 * qpow(s2, p - 2, p) % p;
}
long long lucas(int n, int m) {
  if (m == 0) return 1;
  return getc(n % p, m % p) * lucas(n / p, m / p) % p;
}
int fr[4][1007][1007], fc[4][1007][1007];
int fx[4][1007 << 1][1007 << 1], fy[4][1007 << 1][1007 << 1];
int q[1007][1007];
long long ans2 = 0, ans3 = 0;
double ln2 = log(2), ln3 = log(3);
int c23(long long x2, long long x3) {
  if (x2 <= x3) return -1;
  double ta = (double)x2 * ln2, tb = (double)x3 * ln3;
  if (ta < tb)
    return -1;
  else
    return 1;
}
void update(int i, int j, int M, int o) {
  long long a2, a3;
  if (o == 1) {
    a2 = fc[2][i + M - 1][j] - fc[2][i - M][j] + fr[2][i][j + M - 1] -
         fr[2][i][j - M];
    a3 = fc[3][i + M - 1][j] - fc[3][i - M][j] + fr[3][i][j + M - 1] -
         fr[3][i][j - M];
    if (q[i][j] == 2) --a2;
    if (q[i][j] == 3) --a3;
  }
  if (o == 2) {
    a2 = fx[2][i + M - 1][j + M - 1] - fx[2][i - M][j - M] +
         fy[2][i + M - 1][j - M + 1] - fy[2][i - M][j + M];
    a3 = fx[3][i + M - 1][j + M - 1] - fx[3][i - M][j - M] +
         fy[3][i + M - 1][j - M + 1] - fy[3][i - M][j + M];
    if (q[i][j] == 2) --a2;
    if (q[i][j] == 3) --a3;
  }
  if (a2 >= ans2 && a3 >= ans3) {
    ans2 = a2;
    ans3 = a3;
  }
  if (a2 <= ans2 && a3 <= ans3) return;
  if (a2 < ans2 && a3 > ans3) {
    if (c23(ans2 - a2, a3 - ans3) < 0) ans2 = a2, ans3 = a3;
  }
  if (a2 > ans2 && a3 < ans3) {
    if (c23(a2 - ans2, ans3 - a3) > 0) ans2 = a2, ans3 = a3;
  }
}
int main() {
  int T = 1;
  long long N = 30;
  for (int ci = 1; ci <= T; ++ci) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      char c;
      scanf("%c", &c);
      for (int j = 1; j <= n; ++j) {
        scanf("%c", &c);
        q[i][j] = c - '0';
      }
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        fr[0][i][j] = fr[0][i][j - 1];
        fr[1][i][j] = fr[1][i][j - 1];
        fr[2][i][j] = fr[2][i][j - 1];
        fr[3][i][j] = fr[3][i][j - 1];
        ++fr[q[i][j]][i][j];
        fc[0][j][i] = fc[0][j - 1][i];
        fc[1][j][i] = fc[1][j - 1][i];
        fc[2][j][i] = fc[2][j - 1][i];
        fc[3][j][i] = fc[3][j - 1][i];
        ++fc[q[j][i]][j][i];
      }
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        fx[0][i][j] = fx[0][i - 1][j - 1];
        fx[1][i][j] = fx[1][i - 1][j - 1];
        fx[2][i][j] = fx[2][i - 1][j - 1];
        fx[3][i][j] = fx[3][i - 1][j - 1];
        ++fx[q[i][j]][i][j];
      }
    }
    for (int j = n; j >= 1; --j) {
      for (int i = 1; i <= n; ++i) {
        fy[0][i][j] = fy[0][i - 1][j + 1];
        fy[1][i][j] = fy[1][i - 1][j + 1];
        fy[2][i][j] = fy[2][i - 1][j + 1];
        fy[3][i][j] = fy[3][i - 1][j + 1];
        ++fy[q[i][j]][i][j];
      }
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (q[i][j]) {
          cnt = 1;
          int l, r;
          l = 1;
          r = min(min(i, j), min(n - i + 1, n - j + 1)) + 1;
          while (l + 1 < r) {
            int M = l + r >> 1;
            if (fc[0][i + M - 1][j] - fc[0][i - M][j] == 0 &&
                fr[0][i][j + M - 1] - fr[0][i][j - M] == 0)
              l = M;
            else
              r = M;
          }
          update(i, j, l, 1);
          l = 1;
          r = min(min(i, j), min(n - i + 1, n - j + 1)) + 1;
          while (l + 1 < r) {
            int M = l + r >> 1;
            if (fx[0][i + M - 1][j + M - 1] - fx[0][i - M][j - M] == 0 &&
                fy[0][i + M - 1][j - M + 1] - fy[0][i - M][j + M] == 0)
              l = M;
            else
              r = M;
          }
          update(i, j, l, 2);
        }
      }
    }
    long long u =
        qpow(2, ans2, 1000000007) * qpow(3, ans3, 1000000007) % 1000000007;
    ans = u;
    printf("%d\n", ans * cnt);
  }
  return 0;
}
