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 maps[1010][1010];
int n;
int dir[8][2] = {{0, 1},  {1, 0}, {0, -1}, {-1, 0},
                 {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
int pre[8][1010][1010];
double sums[8][1010][1010];
void partial() {
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (j - dir[i][0] < 0 || j - dir[i][0] >= n || k - dir[i][1] < 0 ||
            k - dir[i][1] >= n)
          for (int x = j, y = k; x >= 0 && x < n && y >= 0 && y < n;
               x += dir[i][0], y += dir[i][1]) {
            if (maps[x][y] == 0) {
              pre[i][x][y] = 0;
              sums[i][x][y] = 0;
            } else {
              if (x == j && y == k) {
                pre[i][x][y] = 1;
                sums[i][x][y] = log(maps[x][y]);
              } else {
                pre[i][x][y] = pre[i][x - dir[i][0]][y - dir[i][1]] + 1;
                sums[i][x][y] =
                    sums[i][x - dir[i][0]][y - dir[i][1]] + log(maps[x][y]);
              }
            }
          }
      }
    }
  }
}
double maxCross(int x, int y) {
  int minN = 1e9, minR = 1e9;
  double rot = log(maps[x][y]), norm = log(maps[x][y]);
  for (int i = 0; i < 4; i++) {
    minN = min(minN, pre[i][x][y]);
  }
  for (int i = 4; i < 8; i++) {
    minR = min(minR, pre[i][x][y]);
  }
  minN--;
  minR--;
  for (int i = 0; i < 4; i++) {
    int sx = x + (dir[i][0] * minN);
    int sy = y + (dir[i][1] * minN);
    norm += sums[i][sx][sy] - sums[i][x][y];
  }
  for (int i = 4; i < 8; i++) {
    int sx = x + (dir[i][0] * minR);
    int sy = y + (dir[i][1] * minR);
    rot += sums[i][sx][sy] - sums[i][x][y];
  }
  return max(norm, rot);
}
bool isNorm(int x, int y) {
  int minN = 1e9, minR = 1e9;
  double rot = log(maps[x][y]), norm = log(maps[x][y]);
  for (int i = 0; i < 4; i++) {
    minN = min(minN, pre[i][x][y]);
  }
  for (int i = 4; i < 8; i++) {
    minR = min(minR, pre[i][x][y]);
  }
  minN--;
  minR--;
  for (int i = 0; i < 4; i++) {
    int sx = x + (dir[i][0] * minN);
    int sy = y + (dir[i][1] * minN);
    norm += sums[i][sx][sy] - sums[i][x][y];
  }
  for (int i = 4; i < 8; i++) {
    int sx = x + (dir[i][0] * minR);
    int sy = y + (dir[i][1] * minR);
    rot += sums[i][sx][sy] - sums[i][x][y];
  }
  return norm > rot;
}
long long calcMax(int x, int y) {
  int minN = 1e9, minR = 1e9;
  long long rot = maps[x][y], norm = maps[x][y];
  for (int i = 0; i < 4; i++) {
    minN = min(minN, pre[i][x][y]);
  }
  for (int i = 4; i < 8; i++) {
    minR = min(minR, pre[i][x][y]);
  }
  minN--;
  minR--;
  for (int i = 0; i < 4; i++) {
    int sx = x;
    int sy = y;
    for (int j = 0; j < minN; j++) {
      sx += dir[i][0];
      sy += dir[i][1];
      norm *= maps[sx][sy];
      norm %= (long long)1e9 + 7;
    }
  }
  for (int i = 4; i < 8; i++) {
    int sx = x;
    int sy = y;
    for (int j = 0; j < minR; j++) {
      sx += dir[i][0];
      sy += dir[i][1];
      rot *= maps[sx][sy];
      rot %= (long long)1e9 + 7;
    }
  }
  return (isNorm(x, y) ? norm : rot);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ;
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      char ch;
      cin >> ch;
      maps[i][j] = ch - '0';
    }
  }
  partial();
  int maxX = 0, maxY = 0;
  double maxVal = -1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (maps[i][j] != 0) {
        double temp = maxCross(i, j);
        if (temp > maxVal) {
          maxVal = temp;
          maxX = i;
          maxY = j;
        }
      }
    }
  }
  cout << calcMax(maxX, maxY) << endl;
}
