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 = acos(-1.0);
int A[2000][2000];
char buf[2000];
int n;
int Up[2000][2000][4];
int Left[2000][2000][4];
int UpLeft[2000][2000][4];
int UpRight[2000][2000][4];
int getUpLeft(int x, int y, int k, int count) {
  int res = UpLeft[x][y][k];
  if (x - count >= 0 && y - count >= 0) {
    res -= UpLeft[x - count][y - count][k];
  }
  return res;
}
int getUpRight(int x, int y, int k, int count) {
  int res = UpRight[x][y][k];
  if (x - count >= 0 && y + count < n) {
    res -= UpRight[x - count][y + count][k];
  }
  return res;
}
int getDownRight(int x, int y, int k, int count) {
  return getUpLeft(x + count - 1, y + count - 1, k, count);
}
int getDownLeft(int x, int y, int k, int count) {
  return getUpRight(x + count - 1, y - count + 1, k, count);
}
bool okD(int x, int y, int count) {
  if (getUpLeft(x, y, 0, count) != 0) return false;
  if (getUpRight(x, y, 0, count) != 0) return false;
  if (getDownLeft(x, y, 0, count) != 0) return false;
  if (getDownRight(x, y, 0, count) != 0) return false;
  return true;
}
pair<int, int> getTotalD(int x, int y, int count) {
  int c3 = 0, c2 = 0;
  c2 = getUpLeft(x, y, 2, count) + getUpRight(x, y, 2, count) +
       getDownLeft(x, y, 2, count) + getDownRight(x, y, 2, count);
  c3 = getUpLeft(x, y, 3, count) + getUpRight(x, y, 3, count) +
       getDownLeft(x, y, 3, count) + getDownRight(x, y, 3, count);
  if (A[x][y] == 3) c3 -= 3;
  if (A[x][y] == 2) c2 -= 3;
  return make_pair(c3, c2);
}
int getUp(int x, int y, int k, int count) {
  int res = Up[x][y][k];
  if (y - count >= 0) {
    res -= Up[x][y - count][k];
  }
  return res;
}
int getLeft(int x, int y, int k, int count) {
  int res = Left[x][y][k];
  if (x - count >= 0) {
    res -= Left[x - count][y][k];
  }
  return res;
}
int getDown(int x, int y, int k, int count) {
  return getUp(x, y + count - 1, k, count);
}
int getRight(int x, int y, int k, int count) {
  return getLeft(x + count - 1, y, k, count);
}
bool ok(int x, int y, int count) {
  if (getLeft(x, y, 0, count) != 0) return false;
  if (getRight(x, y, 0, count) != 0) return false;
  if (getUp(x, y, 0, count) != 0) return false;
  if (getDown(x, y, 0, count) != 0) return false;
  return true;
}
pair<int, int> getTotal(int x, int y, int count) {
  int c2 = 0, c3 = 0;
  c2 = getUp(x, y, 2, count) + getDown(x, y, 2, count) +
       getLeft(x, y, 2, count) + getRight(x, y, 2, count);
  c3 = getUp(x, y, 3, count) + getDown(x, y, 3, count) +
       getLeft(x, y, 3, count) + getRight(x, y, 3, count);
  if (A[x][y] == 3) c3 -= 3;
  if (A[x][y] == 2) c2 -= 3;
  return make_pair(c3, c2);
}
bool more(pair<int, int> a, pair<int, int> b) {
  if (a.first >= b.first && a.second >= b.second) {
    return true;
  }
  if (b.first >= a.first && b.second >= a.second) {
    return false;
  }
  int d1 = abs(a.first - b.first);
  int d2 = abs(a.second - b.second);
  double v1 = log(3.0) * d1;
  double v2 = log(2.0) * d2;
  if (v1 > v2) {
    return a.first > b.first;
  }
  return a.second > b.second;
}
int main(int argc, char* argv[]) {
  scanf("%d", &n);
  int cnt = 0;
  for (int i = (0); i < (n); i++) {
    scanf("%s", buf);
    for (int j = (0); j < (n); j++) {
      A[i][j] = buf[j] - '0';
      cnt += A[i][j] != 0;
    }
  }
  if (cnt == 0) {
    cout << 0 << endl;
    return 0;
  }
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (n); j++) {
      Up[i][j][A[i][j]] = 1;
      Left[i][j][A[i][j]] = 1;
      UpLeft[i][j][A[i][j]] = 1;
      UpRight[i][j][A[i][j]] = 1;
      for (int k = (0); k < (4); k++) {
        if (i != 0) Left[i][j][k] += Left[i - 1][j][k];
        if (j != 0) Up[i][j][k] += Up[i][j - 1][k];
        if (i != 0 && j != 0) UpLeft[i][j][k] += UpLeft[i - 1][j - 1][k];
        if (i != 0 && j != n - 1) UpRight[i][j][k] += UpRight[i - 1][j + 1][k];
      }
    }
  }
  pair<int, int> res = make_pair(0, 0);
  int px, py, pl;
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (n); j++) {
      if (A[i][j] == 0) {
        continue;
      }
      int mm = min(i + 1, j + 1);
      mm = min(mm, n - i);
      mm = min(mm, n - j);
      int l = 1, r = mm + 1;
      while (r - l > 1) {
        int M = (r + l) / 2;
        if (ok(i, j, M)) {
          l = M;
        } else
          r = M;
      }
      pair<int, int> c = getTotal(i, j, l);
      if (more(c, res)) {
        res = c;
        px = i;
        py = j;
        pl = l;
      }
    }
  }
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (n); j++) {
      if (A[i][j] == 0) {
        continue;
      }
      int mm = min(i + 1, j + 1);
      mm = min(mm, n - j);
      mm = min(mm, n - i);
      int l = 1, r = mm + 1;
      while (r - l > 1) {
        int M = (r + l) / 2;
        if (okD(i, j, M)) {
          l = M;
        } else
          r = M;
      }
      pair<int, int> c = getTotalD(i, j, l);
      if (more(c, res)) {
        res = c;
        px = i;
        py = j;
        pl = l;
      }
    }
  }
  long long r = 1;
  for (int i = (0); i < (res.first); i++) {
    r *= 3;
    r %= 1000000007;
  }
  for (int i = (0); i < (res.second); i++) {
    r *= 2;
    r %= 1000000007;
  }
  cout << r << endl;
}
