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 long maxx = 1e3 + 20, mod = 1e9 + 7, lg2 = 301029, lg3 = 477121;
long long sat2[maxx][maxx], sat3[maxx][maxx], sot2[maxx][maxx],
    sot3[maxx][maxx];
long long asl2[maxx][maxx], asl3[maxx][maxx], far2[maxx][maxx],
    far3[maxx][maxx];
long long n, c[maxx][maxx], dp[maxx][maxx][8];
pair<long long, long long> ans;
long long pw(long long a, long long b) {
  if (!b) return 1ll;
  long long x = pw(a, b / 2);
  x = (x * x) % mod;
  if (b % 2) x = (x * a) % mod;
  return x;
}
bool vld(long long x, long long y) {
  return (x >= 0 && x < n && y >= 0 && y < n);
}
pair<long long, long long> get_ans1(long long x, long long y, long long mn) {
  long long x2 = 0, x3 = 0;
  x2 += sat2[x][y + mn] - (vld(x, y - mn - 1) ? sat2[x][y - mn - 1] : 0);
  x2 += sot2[x + mn][y] - (vld(x - mn - 1, y) ? sot2[x - mn - 1][y] : 0);
  x3 += sat3[x][y + mn] - (vld(x, y - mn - 1) ? sat3[x][y - mn - 1] : 0);
  x3 += sot3[x + mn][y] - (vld(x - mn - 1, y) ? sot3[x - mn - 1][y] : 0);
  if (c[x][y] == 2) x2--;
  if (c[x][y] == 3) x3--;
  return make_pair(x2, x3);
}
pair<long long, long long> get_ans2(long long x, long long y, long long mn) {
  long long x2 = 0, x3 = 0;
  x2 += asl2[x + mn][y + mn] -
        (vld(x - mn - 1, y - mn - 1) ? asl2[x - mn - 1][y - mn - 1] : 0);
  x2 += far2[x + mn][y - mn] -
        (vld(x - mn - 1, y + mn + 1) ? far2[x - mn - 1][y + mn + 1] : 0);
  x3 += asl3[x + mn][y + mn] -
        (vld(x - mn - 1, y - mn - 1) ? asl3[x - mn - 1][y - mn - 1] : 0);
  x3 += far3[x + mn][y - mn] -
        (vld(x - mn - 1, y + mn + 1) ? far3[x - mn - 1][y + mn + 1] : 0);
  if (c[x][y] == 2) x2--;
  if (c[x][y] == 3) x3--;
  return make_pair(x2, x3);
}
pair<long long, long long> best(pair<long long, long long> x,
                                pair<long long, long long> y) {
  long long a = x.first, b = x.second, q = y.first, w = y.second;
  if (a >= q && b >= w) return x;
  if (a <= q && b <= w) return y;
  long long r = min(a, q);
  a -= r, q -= r;
  r = min(b, w);
  b -= r, w -= r;
  if (b > 0) {
    long long e1 = b * lg3;
    long long e2 = q * lg2;
    if (e1 >= e2)
      return x;
    else
      return y;
  }
  long long e1 = a * lg2;
  long long e2 = w * lg3;
  if (e1 >= e2) return x;
  return y;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  bool bb = false;
  for (long long i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (long long j = 0; j < n; j++) {
      c[i][j] = (s[j] - '0');
      if (c[i][j] == 1) bb = true;
      sat2[i][j] = (j ? sat2[i][j - 1] : 0) + (c[i][j] == 2);
      sat3[i][j] = (j ? sat3[i][j - 1] : 0) + (c[i][j] == 3);
      sot2[i][j] = (i ? sot2[i - 1][j] : 0) + (c[i][j] == 2);
      sot3[i][j] = (i ? sot3[i - 1][j] : 0) + (c[i][j] == 3);
      asl2[i][j] = ((i && j) ? asl2[i - 1][j - 1] : 0) + (c[i][j] == 2);
      asl3[i][j] = ((i && j) ? asl3[i - 1][j - 1] : 0) + (c[i][j] == 3);
      far2[i][j] =
          (vld(i - 1, j + 1) ? far2[i - 1][j + 1] : 0) + (c[i][j] == 2);
      far3[i][j] =
          (vld(i - 1, j + 1) ? far3[i - 1][j + 1] : 0) + (c[i][j] == 3);
    }
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < n; j++) {
      if (c[i][j] == 0) continue;
      if (!vld(i, j - 1) || c[i][j - 1] == 0)
        dp[i][j][0] = 0;
      else
        dp[i][j][0] = dp[i][j - 1][0] + 1;
      if (!vld(i - 1, j - 1) || c[i - 1][j - 1] == 0)
        dp[i][j][1] = 0;
      else
        dp[i][j][1] = dp[i - 1][j - 1][1] + 1;
      if (!vld(i - 1, j) || c[i - 1][j] == 0)
        dp[i][j][2] = 0;
      else
        dp[i][j][2] = dp[i - 1][j][2] + 1;
      if (!vld(i - 1, j + 1) || c[i - 1][j + 1] == 0)
        dp[i][j][3] = 0;
      else
        dp[i][j][3] = dp[i - 1][j + 1][3] + 1;
    }
  }
  for (long long i = n - 1; i >= 0; i--) {
    for (long long j = n - 1; j >= 0; j--) {
      if (c[i][j] == 0) continue;
      if (!vld(i, j + 1) || c[i][j + 1] == 0)
        dp[i][j][4] = 0;
      else
        dp[i][j][4] = dp[i][j + 1][4] + 1;
      if (!vld(i + 1, j + 1) || c[i + 1][j + 1] == 0)
        dp[i][j][5] = 0;
      else
        dp[i][j][5] = dp[i + 1][j + 1][5] + 1;
      if (!vld(i + 1, j) || c[i + 1][j] == 0)
        dp[i][j][6] = 0;
      else
        dp[i][j][6] = dp[i + 1][j][6] + 1;
      if (!vld(i + 1, j - 1) || c[i + 1][j - 1] == 0)
        dp[i][j][7] = 0;
      else
        dp[i][j][7] = dp[i + 1][j - 1][7] + 1;
    }
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < n; j++) {
      if (!c[i][j]) continue;
      long long mn =
          min(min(dp[i][j][1], dp[i][j][3]), min(dp[i][j][5], dp[i][j][7]));
      pair<long long, long long> x = get_ans2(i, j, mn);
      long long mn2 =
          min(min(dp[i][j][0], dp[i][j][2]), min(dp[i][j][4], dp[i][j][6]));
      pair<long long, long long> y = get_ans1(i, j, mn2);
      ans = best(ans, x);
      ans = best(ans, y);
    }
  }
  if (!ans.first && !ans.second) return cout << bb << endl, 0;
  long long res = 1ll;
  res = (res * pw(2, ans.first)) % mod;
  res = (res * pw(3, ans.second)) % mod;
  cout << res << endl;
  return 0;
}
