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 mod = 1e9 + 7;
const int N = 1005;
pair<int, int> best;
int n, i, j, ans;
char roww[N];
int up[N][N], lf[N][N], rg[N][N], dn[N][N];
int d1[N][N], d2[N][N], d3[N][N], d4[N][N];
pair<int, int> row[N][N], col[N][N];
int a[N][N];
pair<int, int> f1[N][N], f2[N][N], f3[N][N], f4[N][N];
pair<int, int> pairSub(pair<int, int> a, pair<int, int> b) {
  assert(a.first >= b.first);
  assert(a.second >= b.second);
  return make_pair(a.first - b.first, a.second - b.second);
}
void tryUpd(pair<int, int> e) {
  long double have = log(2) * best.first + log(3) * best.second;
  long double my = log(2) * e.first + log(3) * e.second;
  if (my > have) best = e;
}
void trySimple(int x, int y, int sz) {
  if (sz == 1) {
    tryUpd(make_pair(a[x][y] == 2, a[x][y] == 3));
    return;
  }
  pair<int, int> me = make_pair(a[x][y] == 2, a[x][y] == 3);
  pair<int, int> toUp = pairSub(col[y][x - 1], col[y][x - sz]);
  pair<int, int> toDown = pairSub(col[y][x + sz - 1], col[y][x]);
  pair<int, int> toLeft = pairSub(row[x][y - 1], row[x][y - sz]);
  pair<int, int> toRight = pairSub(row[x][y + sz - 1], row[x][y]);
  pair<int, int> kurwa = make_pair(0, 0);
  kurwa.first =
      me.first + toUp.first + toDown.first + toLeft.first + toRight.first;
  kurwa.second =
      me.second + toUp.second + toDown.second + toLeft.second + toRight.second;
  tryUpd(kurwa);
}
void tryRotated(int x, int y, int sz) {
  if (sz == 1) {
    tryUpd(make_pair(a[x][y] == 2, a[x][y] == 3));
    return;
  }
  pair<int, int> me = make_pair(a[x][y] == 2, a[x][y] == 3);
  pair<int, int> to1 = pairSub(f1[x - 1][y - 1], f1[x - sz][y - sz]);
  pair<int, int> to2 = pairSub(f2[x - 1][y + 1], f2[x - sz][y + sz]);
  pair<int, int> to3 = pairSub(f3[x + 1][y - 1], f3[x + sz][y - sz]);
  pair<int, int> to4 = pairSub(f4[x + 1][y + 1], f4[x + sz][y + sz]);
  pair<int, int> kurwa = make_pair(0, 0);
  kurwa.first = to1.first + to2.first + to3.first + to4.first + me.first;
  kurwa.second = to1.second + to2.second + to3.second + to4.second + me.second;
  tryUpd(kurwa);
}
inline void output(pair<int, int> a) {
  long long res = 1;
  for (int i = 0; i < a.first; i++) res = (2 * res) % mod;
  for (int i = 0; i < a.second; i++) res = (3 * res) % mod;
  cout << res << endl;
  exit(0);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", roww + 1);
    for (int j = 1; j <= n; j++) a[i][j] = roww[j] - '0';
  }
  for (int i = 0; i <= n + 1; i++)
    for (int j = 0; j <= n + 1; j++) {
      up[i][j] = lf[i][j] = rg[i][j] = dn[i][j] = -1;
      d1[i][j] = d2[i][j] = d3[i][j] = d4[i][j] = -1;
    }
  {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        if (a[i][j] == 0)
          up[i][j] = i;
        else
          up[i][j] = up[i - 1][j];
      }
    for (int i = n; i >= 1; i--)
      for (int j = 1; j <= n; j++) {
        if (a[i][j] == 0)
          dn[i][j] = i;
        else
          dn[i][j] = dn[i + 1][j];
      }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        if (a[i][j] == 0)
          lf[i][j] = j;
        else
          lf[i][j] = lf[i][j - 1];
      }
    for (int i = 1; i <= n; i++)
      for (int j = n; j >= 1; j--) {
        if (a[i][j] == 0)
          rg[i][j] = j;
        else
          rg[i][j] = rg[i][j + 1];
      }
  }
  {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        if (a[i][j] == 0)
          d1[i][j] = i;
        else
          d1[i][j] = d1[i - 1][j - 1];
      }
    for (int i = 1; i <= n; i++)
      for (int j = n; j >= 1; j--) {
        if (a[i][j] == 0)
          d2[i][j] = i;
        else
          d2[i][j] = d2[i - 1][j + 1];
      }
    for (int i = n; i >= 1; i--)
      for (int j = 1; j <= n; j++) {
        if (a[i][j] == 0)
          d3[i][j] = i;
        else
          d3[i][j] = d3[i + 1][j - 1];
      }
    for (int i = n; i >= 1; i--)
      for (int j = n; j >= 1; j--) {
        if (a[i][j] == 0)
          d4[i][j] = i;
        else
          d4[i][j] = d4[i + 1][j + 1];
      }
  }
  ans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (a[i][j] == 1) ans = 1;
  best = make_pair(0, 0);
  {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        row[i][j] = row[i][j - 1];
        row[i][j].first += (a[i][j] == 2);
        row[i][j].second += (a[i][j] == 3);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        col[j][i] = col[j][i - 1];
        col[j][i].first += (a[i][j] == 2);
        col[j][i].second += (a[i][j] == 3);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (a[i][j] == 0) continue;
        int toUp = i;
        if (up[i][j] != -1) toUp = i - up[i][j];
        int toDown = n - i + 1;
        if (dn[i][j] != -1) toDown = dn[i][j] - i;
        int toLeft = j;
        if (lf[i][j] != -1) toLeft = j - lf[i][j];
        int toRight = n - j + 1;
        if (rg[i][j] != -1) toRight = rg[i][j] - j;
        int sz = min(min(toUp, toDown), min(toLeft, toRight));
        trySimple(i, j, sz);
      }
    }
  }
  {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        f1[i][j] = f1[i - 1][j - 1];
        f1[i][j].first += a[i][j] == 2;
        f1[i][j].second += a[i][j] == 3;
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = n; j >= 1; j--) {
        f2[i][j] = f2[i - 1][j + 1];
        f2[i][j].first += a[i][j] == 2;
        f2[i][j].second += a[i][j] == 3;
      }
    }
    for (int i = n; i >= 1; i--)
      for (int j = 1; j <= n; j++) {
        f3[i][j] = f3[i + 1][j - 1];
        f3[i][j].first += a[i][j] == 2;
        f3[i][j].second += a[i][j] == 3;
      }
    for (int i = n; i >= 1; i--)
      for (int j = n; j >= 1; j--) {
        f4[i][j] = f4[i + 1][j + 1];
        f4[i][j].first += a[i][j] == 2;
        f4[i][j].second += a[i][j] == 3;
      }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (a[i][j] == 0) continue;
        int to1 = min(i, j);
        if (d1[i][j] != -1) to1 = i - d1[i][j];
        int to2 = min(i, n - j + 1);
        if (d2[i][j] != -1) to2 = i - d2[i][j];
        int to3 = min(n - i + 1, j);
        if (d3[i][j] != -1) to3 = d3[i][j] - i;
        int to4 = min(n - i + 1, n - j + 1);
        if (d4[i][j] != -1) to4 = d4[i][j] - i;
        int sz = min(min(to1, to2), min(to3, to4));
        tryRotated(i, j, sz);
      }
    }
  }
  if (best.first > 0 || best.second > 0) {
    output(best);
  } else {
    printf("%d\n", ans);
  }
  return 0;
}
