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 int MAXN = 1e3 + 5;
const double lg2 = log(2), lg3 = log(3);
const long long MOD = 1e9 + 7;
int n, v[MAXN][MAXN];
double logs[MAXN][MAXN], sum[8][MAXN][MAXN];
int cnt[8][MAXN][MAXN];
int dx[8] = {1, 1, -1, -1, -1, 1, 0, 0};
int dy[8] = {1, -1, 1, -1, 0, 0, 1, -1};
inline bool in(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int k = 0; k < n; k++) {
      scanf("%1d", &v[i][k]);
      if (v[i][k] == 2)
        logs[i][k] = lg2;
      else if (v[i][k] == 3)
        logs[i][k] = lg3;
    }
  }
  for (int op = 0; op < 8; op++) {
    int ddx = dx[op];
    int ddy = dy[op];
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < n; k++) {
        if (in(i - ddx, k - ddy)) continue;
        int x = i, y = k, c = 0;
        while (in(x, y)) {
          if (x == i && y == k) {
            sum[op][x][y] = logs[x][y];
            cnt[op][x][y] = 0;
            c = (v[x][y] != 0);
          } else {
            if (v[x][y] != 0) {
              sum[op][x][y] = sum[op][x - ddx][y - ddy] + logs[x][y];
              cnt[op][x][y] = c;
              c++;
            } else {
              c = 0;
              sum[op][x][y] = 0;
              cnt[op][x][y] = c;
            }
          }
          x += ddx;
          y += ddy;
        }
      }
    }
  }
  int ansX = 0, ansY = 0, ansBase = 0, ansSize = 0;
  double ansSum = 0;
  for (int i = 0; i < n; i++) {
    for (int k = 0; k < n; k++) {
      int size[2] = {(int)1e9 + 10, (int)1e9 + 10};
      for (int base = 0; base < 2; base++)
        for (int _op = 0; _op < 4; _op++)
          size[base] = min(size[base], cnt[base * 4 + _op][i][k]);
      for (int base = 0; base < 2; base++) {
        double curSum = logs[i][k];
        for (int _op = 0; _op < 4; _op++) {
          int op = base * 4 + _op;
          int nx = i + dx[op] * (size[base]);
          int ny = k + dy[op] * (size[base]);
          curSum += sum[op][nx][ny] - sum[op][i][k];
        }
        if (curSum >= ansSum) {
          ansSum = curSum;
          ansX = i;
          ansY = k;
          ansBase = base;
          ansSize = size[base];
        }
      }
    }
  }
  long long ans = v[ansX][ansY];
  for (int i = 1; i <= ansSize; i++) {
    for (int _op = 0; _op < 4; _op++) {
      int op = ansBase * 4 + _op;
      ans = (ans * (long long)v[ansX + i * dx[op]][ansY + i * dy[op]]) % MOD;
    }
  }
  printf("%lld\n", ans);
}
