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 C = log2(3);
const int maxn = 1 * 1000 + 10, mod = 1000000007;
int n, r[2][maxn][maxn], c[2][maxn][maxn], arr[3][maxn][maxn];
char ch;
vector<int> vecr[maxn], vecc[maxn];
pair<int, int> mx = {-1, 0}, kmk;
inline bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  return (long double)a.first + (long double)a.second * C >
         (long double)b.first + (long double)b.second * C;
}
pair<int, int> solve(int x) {
  pair<int, int> ans = {-1, 0}, tmp;
  int ja, d;
  for (int i = 0; i < maxn; i++) {
    vecr[i].clear();
    vecc[i].clear();
  }
  for (int i = 0; i < maxn - 1; i++) {
    for (int j = 0; j < maxn - 1; j++) {
      r[0][i][j + 1] = r[0][i][j];
      r[1][i][j + 1] = r[1][i][j];
      c[0][i + 1][j] = c[0][i][j];
      c[1][i + 1][j] = c[1][i][j];
      if (arr[x][i][j] == 0) {
        vecr[i].push_back(j);
        vecc[j].push_back(i);
      } else if (arr[x][i][j] > 1) {
        r[arr[x][i][j] - 2][i][j + 1]++;
        c[arr[x][i][j] - 2][i + 1][j]++;
      }
    }
  }
  for (int i = 0; i < maxn; i++) {
    for (int j = 0; j < maxn; j++) {
      if (arr[x][i][j] != 0) {
        d = mod;
        ja = lower_bound(vecr[i].begin(), vecr[i].end(), j) - vecr[i].begin();
        if (ja == ((int(vecr[i].size()))))
          d = min(d, maxn - j);
        else
          d = min(d, vecr[i][ja] - j);
        if (ja == 0)
          d = min(d, j + 1);
        else
          d = min(d, j - vecr[i][ja - 1]);
        ja = lower_bound(vecc[j].begin(), vecc[j].end(), i) - vecc[j].begin();
        if (ja == ((int(vecc[j].size()))))
          d = min(d, maxn - i);
        else
          d = min(d, vecc[j][ja] - i);
        if (ja == 0)
          d = min(d, i + 1);
        else
          d = min(d, i - vecc[j][ja - 1]);
        tmp.first = r[0][i][j + d] - r[0][i][j + 1] + r[0][i][j] -
                    r[0][i][j - d + 1] + c[0][i + d][j] - c[0][i + 1][j] +
                    c[0][i][j] - c[0][i - d + 1][j];
        tmp.second = r[1][i][j + d] - r[1][i][j + 1] + r[1][i][j] -
                     r[1][i][j - d + 1] + c[1][i + d][j] - c[1][i + 1][j] +
                     c[1][i][j] - c[1][i - d + 1][j];
        if (arr[x][i][j] == 2)
          tmp.first++;
        else if (arr[x][i][j] == 3)
          tmp.second++;
        if (cmp(tmp, ans)) ans = tmp;
      }
    }
  }
  return ans;
}
long long power(int a, int b, int m) {
  if (b == 0) return 1;
  long long hlp = power(a, b / 2, m);
  if (b & 1) return (((hlp * hlp) % m) * a) % m;
  return (hlp * hlp) % m;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> ch;
      arr[2][i][j] = ch - '0';
      arr[(i + j) & 1][(i + j) / 2][(j - i + 1000) / 2] = arr[2][i][j];
    }
  }
  for (int i = 0; i < 3; i++) {
    kmk = solve(i);
    if (cmp(kmk, mx)) mx = kmk;
  }
  if (mx.first == -1)
    cout << 0;
  else
    cout << (power(2, mx.first, mod) * power(3, mx.second, mod)) % mod;
  return 0;
}
