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;
inline int ckmax(int &a, int b) { return a < b ? a = b, 1 : 0; }
inline int ckmin(int &a, int b) { return a > b ? a = b, 1 : 0; }
const int M = 1e9 + 7, N = 1023;
int n, a[N][N];
double b[N][N];
char s[N];
int L[N][N], R[N][N], D[N][N], U[N][N], LU[N][N], LD[N][N], RU[N][N], RD[N][N];
long long l[N][N], r[N][N], d[N][N], u[N][N], lu[N][N], ld[N][N], ru[N][N],
    rd[N][N];
double tl[N][N], tr[N][N], td[N][N], tu[N][N], tlu[N][N], tld[N][N], tru[N][N],
    trd[N][N];
double tans;
int ans;
inline int pow(long long a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = (long long)a * a % M)
    if (b & 1) ans = (long long)ans * a % M;
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s);
    for (int j = 1; j <= n; ++j) {
      a[i][j] = s[j - 1] - '0';
      ans = max(a[i][j], ans);
      b[i][j] = log(a[i][j]);
    }
  }
  for (int i = 0; i <= n + 1; ++i)
    for (int j = 0; j <= n + 1; ++j) {
      l[i][j] = r[i][j] = u[i][j] = d[i][j] = 1;
      lu[i][j] = ru[i][j] = ld[i][j] = rd[i][j] = 1;
    }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (a[i][j])
        L[i][j] = L[i][j - 1] + 1, l[i][j] = l[i][j - 1] * a[i][j] % M,
        tl[i][j] = tl[i][j - 1] + b[i][j];
      if (a[i][j])
        LU[i][j] = LU[i - 1][j - 1] + 1,
        lu[i][j] = lu[i - 1][j - 1] * a[i][j] % M,
        tlu[i][j] = tlu[i - 1][j - 1] + b[i][j];
    }
  }
  for (int i = n; i >= 1; --i) {
    for (int j = n; j >= 1; --j) {
      if (a[i][j])
        R[i][j] = R[i][j + 1] + 1, r[i][j] = r[i][j + 1] * a[i][j] % M,
        tr[i][j] = tr[i][j + 1] + b[i][j];
      if (a[i][j])
        RD[i][j] = RD[i + 1][j + 1] + 1,
        rd[i][j] = rd[i + 1][j + 1] * a[i][j] % M,
        trd[i][j] = trd[i + 1][j + 1] + b[i][j];
    }
  }
  for (int j = n; j >= 1; --j) {
    for (int i = 1; i <= n; ++i) {
      if (a[i][j])
        U[i][j] = U[i - 1][j] + 1, u[i][j] = u[i - 1][j] * a[i][j] % M,
        tu[i][j] = tu[i - 1][j] + b[i][j];
      if (a[i][j])
        RU[i][j] = RU[i - 1][j + 1] + 1,
        ru[i][j] = ru[i - 1][j + 1] * a[i][j] % M,
        tru[i][j] = tru[i - 1][j + 1] + b[i][j];
    }
  }
  for (int j = 1; j <= n; ++j) {
    for (int i = n; i >= 1; --i) {
      if (a[i][j])
        D[i][j] = D[i + 1][j] + 1, d[i][j] = d[i + 1][j] * a[i][j] % M,
        td[i][j] = td[i + 1][j] + b[i][j];
      if (a[i][j])
        LD[i][j] = LD[i + 1][j - 1] + 1,
        ld[i][j] = ld[i + 1][j - 1] * a[i][j] % M,
        tld[i][j] = tld[i + 1][j - 1] + b[i][j];
    }
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      if (!a[i][j]) continue;
      int dd = min(min(L[i][j], R[i][j]), min(U[i][j], D[i][j]));
      double tres = tl[i][j] + tr[i][j] + tu[i][j] + td[i][j] - tl[i][j - dd] -
                    tr[i][j + dd] - tu[i - dd][j] - td[i + dd][j] - 3 * b[i][j];
      if (tres > tans) {
        tans = tres;
        int t = pow((long long)a[i][j], M - 2);
        long long res = l[i][j] * r[i][j] % M * u[i][j] % M * d[i][j] % M;
        res = res * pow(l[i][j - dd], M - 2) % M;
        res = res * pow(r[i][j + dd], M - 2) % M;
        res = res * pow(u[i - dd][j], M - 2) % M;
        res = res * pow(d[i + dd][j], M - 2) % M;
        res = res * t % M * t % M * t % M;
        ans = res;
      }
      dd = min(min(LU[i][j], LD[i][j]), min(RU[i][j], RD[i][j]));
      tres = tlu[i][j] + tld[i][j] + tru[i][j] + trd[i][j] -
             tlu[i - dd][j - dd] - tld[i + dd][j - dd] - tru[i - dd][j + dd] -
             trd[i + dd][j + dd] - 3 * b[i][j];
      if (tres > tans) {
        tans = tres;
        int t = pow((long long)a[i][j], M - 2);
        long long res = lu[i][j] * ld[i][j] % M * ru[i][j] % M * rd[i][j] % M;
        res = res * pow(lu[i - dd][j - dd], M - 2) % M;
        res = res * pow(ld[i + dd][j - dd], M - 2) % M;
        res = res * pow(ru[i - dd][j + dd], M - 2) % M;
        res = res * pow(rd[i + dd][j + dd], M - 2) % M;
        res = res * t % M * t % M * t % M;
        ans = res;
      }
    }
  cout << ans;
  return 0;
}
