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 int maxn = 1010;
const int MOD = 1000000007;
struct modn {
  int n;
  modn() {}
  modn(long long x) {
    n = (x >= 0 ? (x < MOD ? x : x % MOD) : (x % MOD + MOD) % MOD);
  }
  bool operator<(const modn& B) { return n < B.n; }
  bool operator==(const modn& B) { return n == B.n; }
  bool operator!=(const modn& B) { return n != B.n; }
  modn operator+(const modn& B) {
    return modn(n + B.n < MOD ? n + B.n : n + B.n - MOD);
  }
  modn operator-(const modn& B) {
    return modn(0 <= n - B.n ? n - B.n : n - B.n + MOD);
  }
  modn operator*(const modn& B) { return modn((long long)n * B.n); }
  modn& operator+=(const modn& B) { return *this = *this + B; }
  modn& operator-=(const modn& B) { return *this = *this - B; }
  modn& operator*=(const modn& B) { return *this = *this * B; }
  modn& operator-() {
    n = MOD - n;
    return *this;
  }
  void print() const { printf("%d\n", n); }
};
modn pow_mod(const modn& A, long long x) {
  modn s = 1, t = A;
  for (; x; x >>= 1) {
    if (x & 1) s *= t;
    t *= t;
  }
  return s;
}
struct node {
  int a, b;
  node() : a(0), b(0) {}
  node(int x) : a(x == 2), b(x == 3) {}
  node(int a, int b) : a(a), b(b) {}
  bool operator<(const node& B) {
    return a * log(2) + b * log(3) < B.a * log(2) + B.b * log(3);
  }
  node operator+(const node& B) { return node(a + B.a, b + B.b); }
  node operator-(const node& B) { return node(a - B.a, b - B.b); }
};
int n;
char a[maxn][maxn];
node Lp[maxn][maxn], Up[maxn][maxn];
int L[maxn][maxn], R[maxn][maxn], U[maxn][maxn], D[maxn][maxn];
node Px(int i, int j1, int j2) { return Lp[i][j2] - Lp[i][j1 - 1]; }
node Py(int j, int i1, int i2) { return Up[i2][j] - Up[i1 - 1][j]; }
void solve() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%s", &a[i][1]);
  node res(-1, -1);
  memset(L, 0, sizeof L);
  memset(R, 0, sizeof R);
  memset(Lp, 0, sizeof Lp);
  memset(U, 0, sizeof U);
  memset(D, 0, sizeof D);
  memset(Up, 0, sizeof Up);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j)
      L[i][j] = (a[i][j] == '0' ? 0 : L[i][j - 1] + 1);
    for (int j = n; j >= 1; --j)
      R[i][j] = (a[i][j] == '0' ? 0 : R[i][j + 1] + 1);
    for (int j = 1; j <= n; ++j)
      Lp[i][j] =
          (a[i][j] == '0' ? Lp[i][j - 1] : Lp[i][j - 1] + (a[i][j] - '0'));
  }
  for (int j = 1; j <= n; ++j) {
    for (int i = 1; i <= n; ++i)
      U[i][j] = (a[i][j] == '0' ? 0 : U[i - 1][j] + 1);
    for (int i = n; i >= 1; --i)
      D[i][j] = (a[i][j] == '0' ? 0 : D[i + 1][j] + 1);
    for (int i = 1; i <= n; ++i)
      Up[i][j] =
          (a[i][j] == '0' ? Up[i - 1][j] : Up[i - 1][j] + (a[i][j] - '0'));
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      if (a[i][j] != '0') {
        int x = min(min(L[i][j], R[i][j]), min(U[i][j], D[i][j]));
        node s = Px(i, j - x + 1, j + x - 1) + Py(j, i - x + 1, i + x - 1) -
                 (a[i][j] - '0');
        if (res < s) res = s;
      }
  memset(L, 0, sizeof L);
  memset(R, 0, sizeof R);
  memset(Lp, 0, sizeof Lp);
  memset(U, 0, sizeof U);
  memset(D, 0, sizeof D);
  memset(Up, 0, sizeof Up);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j)
      L[i][j] = (a[i][j] == '0' ? 0 : L[i - 1][j - 1] + 1);
    for (int j = 1; j <= n; ++j)
      Lp[i][j] = (a[i][j] == '0' ? Lp[i - 1][j - 1]
                                 : Lp[i - 1][j - 1] + (a[i][j] - '0'));
  }
  for (int i = n; i >= 1; --i) {
    for (int j = 1; j <= n; ++j)
      R[i][j] = (a[i][j] == '0' ? 0 : R[i + 1][j + 1] + 1);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j)
      U[i][j] = (a[i][j] == '0' ? 0 : U[i - 1][j + 1] + 1);
    for (int j = 1; j <= n; ++j)
      Up[i][j] = (a[i][j] == '0' ? Up[i - 1][j + 1]
                                 : Up[i - 1][j + 1] + (a[i][j] - '0'));
  }
  for (int i = n; i >= 1; --i) {
    for (int j = 1; j <= n; ++j)
      D[i][j] = (a[i][j] == '0' ? 0 : D[i + 1][j - 1] + 1);
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      if (a[i][j] != '0') {
        if (i == 3 && j == 3) {
          int pp = 1;
        }
        int x = min(min(L[i][j], R[i][j]), min(U[i][j], D[i][j]));
        node s = (Lp[i + x - 1][j + x - 1] - Lp[i - x][j - x]) +
                 (Up[i + x - 1][j - x + 1] - Up[i - x][j + x]) -
                 (a[i][j] - '0');
        if (res < s) res = s;
      }
  if (res.a == -1)
    puts("0");
  else
    (pow_mod(2LL, res.a) * pow_mod(3LL, res.b)).print();
}
int main() {
  solve();
  return 0;
}
