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;
int dir[8][2] = {{0, 1}, {1, 0},  {-1, 0}, {0, -1},
                 {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int n;
int t[1001][1001];
int tZero[1001][1001][8];
double tSum[1001][1001][8];
bool markSum[1001][1001][8];
double GetLog(int x) {
  if (x == 1)
    return 0;
  else if (x == 2)
    return 0.30102999566398119521373889472449;
  else if (x == 3)
    return 0.47712125471966243729502790325512;
}
bool IsValid(int x, int y) { return (0 <= x && x < n && 0 <= y && y < n); }
int GetZeros(int i, int j, int d) {
  if (!IsValid(i, j)) return 0;
  if (tZero[i][j][d] != -1) return tZero[i][j][d];
  tZero[i][j][d] =
      t[i][j] == 0 ? 0 : GetZeros(i - dir[d][0], j - dir[d][1], d) + 1;
  return tZero[i][j][d];
}
double GetSum(int i, int j, int d) {
  if (!IsValid(i, j)) return 0;
  if (markSum[i][j][d] == true) return tSum[i][j][d];
  tSum[i][j][d] =
      t[i][j] == 0 ? GetSum(i - dir[d][0], j - dir[d][1], d)
                   : GetSum(i - dir[d][0], j - dir[d][1], d) + GetLog(t[i][j]);
  markSum[i][j][d] = true;
  return tSum[i][j][d];
}
double CalcSumN(int i, int j, int c) {
  return GetSum(i + c, j, 1) - GetSum(i - c - 1, j, 1) + GetSum(i, j + c, 0) -
         GetSum(i, j - c - 1, 0) - GetLog(t[i][j]);
}
double CalcSumR(int i, int j, int c) {
  return GetSum(i + c, j + c, 4) - GetSum(i - c - 1, j - c - 1, 4) +
         GetSum(i + c, j - c, 5) - GetSum(i - c - 1, j + c + 1, 5) -
         GetLog(t[i][j]);
}
int main() {
  cin >> n;
  char ch;
  bool allZero = true;
  memset(tZero, -1, sizeof(tZero));
  memset(tSum, 0, sizeof(tSum));
  memset(markSum, false, sizeof(markSum));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> ch;
      if (ch != '0') allZero = false;
      t[i][j] = ch - '0';
    }
  }
  int maxI = 1, maxJ = 1, maxR = 0;
  double maxi = 0;
  char maxType = 'R';
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (t[i][j] > 0) {
        int maxCN = 2000000;
        for (int k = 0; k < 4; k++) maxCN = min<int>(maxCN, GetZeros(i, j, k));
        int maxCR = 2000000;
        for (int k = 4; k < 8; k++) maxCR = min<int>(maxCR, GetZeros(i, j, k));
        maxCN--;
        maxCR--;
        double CN = CalcSumN(i, j, maxCN);
        double CR = CalcSumR(i, j, maxCR);
        if (CN > maxi) {
          maxi = CN;
          maxI = i;
          maxJ = j;
          maxType = 'N', maxR = maxCN;
        }
        if (CR > maxi) {
          maxi = CR;
          maxI = i;
          maxJ = j;
          maxType = 'R', maxR = maxCR;
        }
      }
    }
  }
  long long ret = t[maxI][maxJ];
  if (maxType == 'R') {
    for (int k = 1; k <= maxR; k++) {
      for (int d = 4; d < 8; d++) {
        ret =
            (ret * t[maxI + k * dir[d][0]][maxJ + k * dir[d][1]]) % 1000000007;
      }
    }
  } else {
    for (int k = 1; k <= maxR; k++) {
      for (int d = 0; d < 4; d++) {
        ret =
            (ret * t[maxI + k * dir[d][0]][maxJ + k * dir[d][1]]) % 1000000007;
      }
    }
  }
  if (ret == 0 && !allZero)
    cout << 1 << endl;
  else
    cout << ret << endl;
  return 0;
}
