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 long double LG2 = log(2.0);
const long double LG3 = log(3.0);
struct Lol {
  int a[4];
  Lol(int x = 0) {
    memset(a, 0, sizeof(a));
    a[x]++;
  }
  Lol operator+(const Lol &x) {
    Lol ret;
    for (int i = 0; i < 4; i++) {
      ret.a[i] = a[i] + x.a[i];
    }
    return ret;
  }
  Lol operator-(const Lol &x) {
    Lol ret;
    for (int i = 0; i < 4; i++) {
      ret.a[i] = a[i] - x.a[i];
    }
    return ret;
  }
};
inline bool lessThan(Lol &x, Lol &y) {
  if (x.a[0]) {
    if (y.a[0]) return false;
    return (y.a[1] > 0) || (y.a[2] > 0) || (y.a[3] > 0);
  }
  if (y.a[0]) return false;
  int x1 = x.a[2], x2 = x.a[3];
  int y1 = y.a[2], y2 = y.a[3];
  if (x1 <= y1 && x2 <= y2) {
    return (x1 != y1) || (x2 != y2);
  }
  if (x1 >= y1 && x2 >= y2) {
    return false;
  }
  if (x1 < y1) {
    return (x2 - y2) * LG3 < (y1 - x1) * LG2;
  }
  return (x1 - y1) * LG2 < (y2 - x2) * LG3;
}
const int N = 1005;
const long long mod = 1000000007;
int arr[N][N], a[N][N];
int nl[N][N], nr[N][N], nu[N][N], nd[N][N];
int nlu[N][N], nru[N][N], nld[N][N], nrd[N][N];
Lol cl[N][N], cu[N][N], clu[N][N], cru[N][N];
Lol func(int n) {
  memset(nl, 0, sizeof(nl));
  memset(nr, 0, sizeof(nr));
  memset(nu, 0, sizeof(nu));
  memset(nd, 0, sizeof(nd));
  memset(nlu, 0, sizeof(nlu));
  memset(nld, 0, sizeof(nld));
  memset(nru, 0, sizeof(nru));
  memset(nrd, 0, sizeof(nrd));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      nl[i][j] = (arr[i][j] == 0) ? 0 : (nl[i][j - 1] + 1);
      nu[i][j] = (arr[i][j] == 0) ? 0 : (nu[i - 1][j] + 1);
      nlu[i][j] = (arr[i][j] == 0) ? 0 : (nlu[i - 1][j - 1] + 1);
      nru[i][j] = (arr[i][j] == 0) ? 0 : (nru[i - 1][j + 1] + 1);
      cl[i][j] = cl[i][j - 1] + Lol(arr[i][j]);
      cu[i][j] = cu[i - 1][j] + Lol(arr[i][j]);
      clu[i][j] = clu[i - 1][j - 1] + Lol(arr[i][j]);
      cru[i][j] = cru[i - 1][j + 1] + Lol(arr[i][j]);
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = n; j >= 1; j--) {
      nr[i][j] = (arr[i][j] == 0) ? 0 : (nr[i][j + 1] + 1);
      nd[i][j] = (arr[i][j] == 0) ? 0 : (nd[i + 1][j] + 1);
      nld[i][j] = (arr[i][j] == 0) ? 0 : (nld[i + 1][j - 1] + 1);
      nrd[i][j] = (arr[i][j] == 0) ? 0 : (nrd[i + 1][j + 1] + 1);
    }
  }
  Lol ret;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!arr[i][j]) continue;
      int d = min(min(nl[i][j], nr[i][j]), min(nu[i][j], nd[i][j])) - 1;
      Lol tmp =
          cl[i][j + d] - cl[i][j - d - 1] + cu[i + d][j] - cu[i - d - 1][j];
      tmp = tmp - Lol(arr[i][j]);
      if (lessThan(ret, tmp)) ret = tmp;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!arr[i][j]) continue;
      int d = min(min(nlu[i][j], nru[i][j]), min(nld[i][j], nrd[i][j])) - 1;
      Lol tmp = clu[i + d][j + d] - clu[i - d - 1][j - d - 1];
      tmp = tmp + cru[i + d][j - d] - cru[i - d - 1][j + d + 1];
      tmp = tmp - Lol(arr[i][j]);
      if (lessThan(ret, tmp)) ret = tmp;
    }
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << setprecision(32);
  int n;
  char ch;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> ch;
      arr[i][j] = ch - '0';
    }
  }
  Lol ans = func(n);
  if (ans.a[0]) {
    cout << 0 << endl;
  } else {
    long long ret = 1;
    while (ans.a[2]--) ret = (ret * 2) % mod;
    while (ans.a[3]--) ret = (ret * 3) % mod;
    cout << ret << endl;
  }
  return 0;
}
