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>
int setBit(int N, int pos) { return N = N | (1 << pos); }
int resetBit(int N, int pos) { return N = N & ~(1 << pos); }
bool checkBit(int N, int pos) { return (bool)(N & (1 << pos)); }
using namespace std;
int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1};
const int MAX = 1005;
const long long int MOD = 1000000007;
int n, arr[MAX][MAX], cum[MAX][MAX][5][5];
double lg[5][MAX * 2];
int save[MAX][MAX][2][5];
inline bool isValid(pair<int, int> p) {
  return (p.first >= 0 && p.first < n && p.second >= 0 && p.second < n);
}
void pre() {
  int i, j, k, l;
  lg[2][0] = 0;
  lg[3][0] = 0;
  for (i = 1; i <= n + n + 2; i++) {
    lg[2][i] = lg[2][i - 1] + log(2);
    lg[3][i] = lg[3][i - 1] + log(3);
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      for (k = 0; k < 4; k++) {
        cum[i][j][k][arr[i][j]]++;
      }
      for (k = 0; k < 4; k++) {
        cum[i][j][0][k] += cum[i][j - 1][0][k];
        cum[i][j][1][k] += cum[i - 1][j][1][k];
        cum[i][j][2][k] += cum[i - 1][j - 1][2][k];
        cum[i][j][3][k] += cum[i - 1][j + 1][3][k];
      }
    }
  }
}
inline bool check(int x, int y, int type, int mid) {
  pair<int, int> p, q;
  int val;
  if (type == 0) {
    p = {x, y - mid};
    q = {x, y + mid};
    if (!isValid(p) || !isValid(q)) return false;
    val = abs(cum[q.first][q.second][0][0] - cum[p.first][p.second][0][0]);
    if (arr[x][y] == 0) val--;
    if (arr[p.first][p.second] == 0) val++;
    if (val != 0) return false;
    p = {x - mid, y};
    q = {x + mid, y};
    if (!isValid(p) || !isValid(q)) return false;
    val = abs(cum[q.first][q.second][1][0] - cum[p.first][p.second][1][0]);
    if (arr[x][y] == 0) val--;
    if (arr[p.first][p.second] == 0) val++;
    if (val != 0) return false;
    return true;
  } else {
    p = {x - mid, y - mid};
    q = {x + mid, y + mid};
    if (!isValid(p) || !isValid(q)) return false;
    val = abs(cum[q.first][q.second][2][0] - cum[p.first][p.second][2][0]);
    if (arr[x][y] == 0) val--;
    if (arr[p.first][p.second] == 0) val++;
    if (val != 0) return false;
    p = {x - mid, y + mid};
    q = {x + mid, y - mid};
    if (!isValid(p) || !isValid(q)) return false;
    val = abs(cum[q.first][q.second][3][0] - cum[p.first][p.second][3][0]);
    if (arr[x][y] == 0) val--;
    if (arr[p.first][p.second] == 0) val++;
    if (val != 0) return false;
    return true;
  }
}
inline int bs(int x, int y, int type) {
  int low = 0, high = n + 1, mid, ret = 0;
  while (low <= high) {
    mid = (low + high) >> 1;
    if (check(x, y, type, mid)) {
      ret = max(ret, mid);
      low = mid + 1;
    } else
      high = mid - 1;
  }
  return ret;
}
inline void fuck(int x, int y, int type) {
  int r = bs(x, y, type);
  pair<int, int> p, q;
  int i, j;
  save[x][y][type][arr[x][y]]++;
  if (r < 1) return;
  if (type == 0) {
    p = {x, y - r};
    q = {x, y + r};
    for (i = 0; i < 4; i++) {
      save[x][y][type][i] +=
          abs(cum[q.first][q.second][0][i] - cum[p.first][p.second][0][i]);
      if (arr[x][y] == i) save[x][y][type][i]--;
      if (arr[p.first][p.second] == i) save[x][y][type][i]++;
    }
    p = {x - r, y};
    q = {x + r, y};
    for (i = 0; i < 4; i++) {
      save[x][y][type][i] +=
          abs(cum[q.first][q.second][1][i] - cum[p.first][p.second][1][i]);
      if (arr[x][y] == i) save[x][y][type][i]--;
      if (arr[p.first][p.second] == i) save[x][y][type][i]++;
    }
  } else {
    p = {x - r, y - r};
    q = {x + r, y + r};
    for (i = 0; i < 4; i++) {
      save[x][y][type][i] +=
          abs(cum[q.first][q.second][2][i] - cum[p.first][p.second][2][i]);
      if (arr[x][y] == i) save[x][y][type][i]--;
      if (arr[p.first][p.second] == i) save[x][y][type][i]++;
    }
    p = {x - r, y + r};
    q = {x + r, y - r};
    for (i = 0; i < 4; i++) {
      save[x][y][type][i] +=
          abs(cum[q.first][q.second][3][i] - cum[p.first][p.second][3][i]);
      if (arr[x][y] == i) save[x][y][type][i]--;
      if (arr[p.first][p.second] == i) save[x][y][type][i]++;
    }
  }
}
inline double here(short x, short y, short z) {
  return lg[2][save[x][y][z][2]] + lg[3][save[x][y][z][3]];
}
void maximize() {
  short i, j, k, mxX = 0, mxY = 0, mxZ = 0;
  double mx = 0;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      for (k = 0; k < 2; k++) {
        double val = here(i, j, k);
        if (val > mx + 1e-9) {
          mx = val;
          mxX = i;
          mxY = j;
          mxZ = k;
        }
      }
    }
  }
  long long int ans = 1;
  while (save[mxX][mxY][mxZ][2]--) {
    ans *= 2;
    ans %= MOD;
  }
  while (save[mxX][mxY][mxZ][3]--) {
    ans *= 3;
    ans %= MOD;
  }
  printf("%I64d\n", ans);
}
int main() {
  int i, j, mx = 0;
  char str[MAX];
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%s", str);
    for (j = 0; j < n; j++) {
      arr[i][j] = str[j] - '0';
      mx = max(mx, arr[i][j]);
    }
  }
  if (mx < 2) {
    printf("%d\n", mx);
    return 0;
  }
  pre();
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      if (arr[i][j]) {
        fuck(i, j, 0);
        fuck(i, j, 1);
      }
    }
  }
  maximize();
  return 0;
}
