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 mod = 1000000007;
int a2, a3;
int n, l, r, mid;
int row[4][1009][1009];
int col[4][1009][1009];
int qqq[4][1009][1009];
int www[4][1009][1009];
long double l2, l3;
int ans2, ans3, ans;
char s[1009][1009];
void zz(int a, int b) {
  if (a >= ans2 && b >= ans3) {
    ans2 = a;
    ans3 = b;
    return;
  }
  if (a * l2 + b * l3 > ans2 * l2 + ans3 * l3) {
    ans2 = a;
    ans3 = b;
  }
}
long long mo(long long a, int x) {
  long long s = 1;
  while (x) {
    if (x & 1) s = s * a % mod;
    x >>= 1;
    a = a * a % mod;
  }
  return s;
}
int main() {
  l2 = logl(2);
  l3 = logl(3);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s[i] + 1);
    for (int j = 1; j <= n; ++j) {
      for (int k = 0; k < 4; ++k) {
        row[k][i][j] = row[k][i][j - 1];
        col[k][i][j] = col[k][i - 1][j];
        qqq[k][i][j] = qqq[k][i - 1][j - 1];
        www[k][i][j] = www[k][i - 1][j + 1];
      }
      row[s[i][j] - '0'][i][j]++;
      col[s[i][j] - '0'][i][j]++;
      qqq[s[i][j] - '0'][i][j]++;
      www[s[i][j] - '0'][i][j]++;
      if (s[i][j] != '0') ans = 1;
    }
  }
  if (ans == 0) {
    printf("0\n");
    return 0;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (s[i][j] == '0') continue;
      l = 0;
      r = min(min(n - i, n - j), min(i - 1, j - 1));
      while (l < r) {
        mid = (l + r + 1) >> 1;
        if (row[0][i][j + mid] - row[0][i][j - mid - 1] == 0 &&
            col[0][i + mid][j] - col[0][i - mid - 1][j] == 0)
          l = mid;
        else
          r = mid - 1;
      }
      a2 = row[2][i][j + l] - row[2][i][j - l - 1] + col[2][i + l][j] -
           col[2][i - l - 1][j];
      a3 = row[3][i][j + l] - row[3][i][j - l - 1] + col[3][i + l][j] -
           col[3][i - l - 1][j];
      if (s[i][j] == '2')
        a2--;
      else if (s[i][j] == '3')
        a3--;
      zz(a2, a3);
      l = 0;
      r = min(min(n - i, n - j), min(i - 1, j - 1));
      while (l < r) {
        mid = (l + r + 1) >> 1;
        if (qqq[0][i + mid][j + mid] - qqq[0][i - mid - 1][j - mid - 1] == 0 &&
            www[0][i + mid][j - mid] - www[0][i - mid - 1][j + mid + 1] == 0)
          l = mid;
        else
          r = mid - 1;
      }
      a2 = qqq[2][i + l][j + l] - qqq[2][i - l - 1][j - l - 1] +
           www[2][i + l][j - l] - www[2][i - l - 1][j + l + 1];
      a3 = qqq[3][i + l][j + l] - qqq[3][i - l - 1][j - l - 1] +
           www[3][i + l][j - l] - www[3][i - l - 1][j + l + 1];
      if (s[i][j] == '2')
        a2--;
      else if (s[i][j] == '3')
        a3--;
      zz(a2, a3);
    }
  }
  printf("%I64d\n", mo(2, ans2) * mo(3, ans3) % mod);
  return 0;
}
