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>
const double ln2 = std::log(2.0);
const double ln3 = std::log(3.0);
char C[1000][1000];
int H[4][1000][1000];
int V[4][1000][1000];
int D1[4][1000][1000];
int D2[4][1000][1000];
int MNR[1000][1000];
int MRR[1000][1000];
int hcount(int v, int i, int a, int b) {
  return H[v][i][b] - H[v][i][a] + (C[i][a] - '0' == v);
}
int vcount(int v, int j, int a, int b) {
  return V[v][b][j] - V[v][a][j] + (C[a][j] - '0' == v);
}
int d1count(int v, int i, int j, int r) {
  return D1[v][i + r][j + r] - D1[v][i - r][j - r] +
         (C[i - r][j - r] - '0' == v);
}
int d2count(int v, int i, int j, int r) {
  return D2[v][i + r][j - r] - D2[v][i - r][j + r] +
         (C[i - r][j + r] - '0' == v);
}
bool validnr(int i, int j, int r) {
  return hcount(0, i, j - r, j + r) == 0 && vcount(0, j, i - r, i + r) == 0;
}
bool validrr(int i, int j, int r) {
  return d1count(0, i, j, r) == 0 && d2count(0, i, j, r) == 0;
}
double calcn(int i, int j) {
  int c2 = hcount(2, i, j - MNR[i][j], j + MNR[i][j]) +
           vcount(2, j, i - MNR[i][j], i + MNR[i][j]) - (C[i][j] == '2');
  int c3 = hcount(3, i, j - MNR[i][j], j + MNR[i][j]) +
           vcount(3, j, i - MNR[i][j], i + MNR[i][j]) - (C[i][j] == '3');
  return double(c2) * ln2 + double(c3) * ln3;
}
double calcr(int i, int j) {
  int c2 = d1count(2, i, j, MRR[i][j]) + d2count(2, i, j, MRR[i][j]) -
           (C[i][j] == '2');
  int c3 = d1count(3, i, j, MRR[i][j]) + d2count(3, i, j, MRR[i][j]) -
           (C[i][j] == '3');
  return double(c2) * ln2 + double(c3) * ln3;
}
bool better(int besti, int bestj, int curri, int currj) {
  if (C[curri][currj] == '0') {
    return false;
  }
  if (C[besti][bestj] == '0') {
    return true;
  }
  double curr = std::max(calcn(curri, currj), calcr(curri, currj));
  double best = std::max(calcn(besti, bestj), calcr(besti, bestj));
  return curr > best;
}
bool betterr(int besti, int bestj, int curri, int currj) {
  if (C[curri][currj] == '0') {
    return false;
  }
  if (C[besti][bestj] == '0') {
    return true;
  }
  return calcr(curri, currj) > calcr(besti, bestj);
}
int maxnr(int n, int i, int j) {
  int lr = 0;
  int hr = std::min(std::min(i, n - 1 - i), std::min(j, n - 1 - j));
  for (;;) {
    int mr = (lr + hr) / 2;
    if (lr == mr) {
      return validnr(i, j, hr) ? hr : lr;
    }
    if (validnr(i, j, mr)) {
      lr = mr;
    } else {
      hr = mr;
    }
  }
}
int maxrr(int n, int i, int j) {
  int lr = 0;
  int hr = std::min(std::min(i, j), std::min(n - 1 - i, n - 1 - j));
  for (;;) {
    int mr = (lr + hr) / 2;
    if (lr == mr) {
      return validrr(i, j, hr) ? hr : lr;
    }
    if (validrr(i, j, mr)) {
      lr = mr;
    } else {
      hr = mr;
    }
  }
}
int main() {
  int n;
  std::cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      std::cin >> C[i][j];
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      H[C[i][j] - '0'][i][j]++;
      if (j > 0) {
        for (int v = 0; v < 4; v++) {
          H[v][i][j] += H[v][i][j - 1];
        }
      }
    }
  }
  for (int j = 0; j < n; j++) {
    for (int i = 0; i < n; i++) {
      V[C[i][j] - '0'][i][j]++;
      if (i > 0) {
        for (int v = 0; v < 4; v++) {
          V[v][i][j] += V[v][i - 1][j];
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      D1[C[i][j] - '0'][i][j]++;
      if (i > 0 && j > 0) {
        for (int v = 0; v < 4; v++) {
          D1[v][i][j] += D1[v][i - 1][j - 1];
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = n - 1; j >= 0; j--) {
      D2[C[i][j] - '0'][i][j]++;
      if (i > 0 && j < n - 1) {
        for (int v = 0; v < 4; v++) {
          D2[v][i][j] += D2[v][i - 1][j + 1];
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      MNR[i][j] = maxnr(n, i, j);
      MRR[i][j] = maxrr(n, i, j);
    }
  }
  int besti = 0, bestj = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (better(besti, bestj, i, j)) {
        besti = i;
        bestj = j;
      }
    }
  }
  int64_t r = 1;
  if (calcn(besti, bestj) >= calcr(besti, bestj)) {
    int bestr = MNR[besti][bestj];
    for (int i = besti - bestr; i <= besti + bestr; i++) {
      r = (r * (C[i][bestj] - '0')) % 1000000007;
    }
    for (int j = bestj - bestr; j < bestj; j++) {
      r = (r * (C[besti][j] - '0')) % 1000000007;
    }
    for (int j = bestj + 1; j <= bestj + bestr; j++) {
      r = (r * (C[besti][j] - '0')) % 1000000007;
    }
  } else {
    int bestr = MRR[besti][bestj];
    r = (r * (C[besti][bestj] - '0')) % 1000000007;
    for (int x = 1; x <= bestr; x++) {
      r = (r * (C[besti - x][bestj - x] - '0')) % 1000000007;
    }
    for (int x = 1; x <= bestr; x++) {
      r = (r * (C[besti + x][bestj + x] - '0')) % 1000000007;
    }
    for (int x = 1; x <= bestr; x++) {
      r = (r * (C[besti - x][bestj + x] - '0')) % 1000000007;
    }
    for (int x = 1; x <= bestr; x++) {
      r = (r * (C[besti + x][bestj - x] - '0')) % 1000000007;
    }
  }
  std::cout << r << "\n";
  return 0;
}
