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;
long long i, j, n, h, x, y, cur_h, k, dir;
long long pre[8][1005][1005];
double sums[8][1005][1005], ans, logs[1005][1005], lg2, lg3;
long long ansx, ansy, anssize, ansdir;
long long total;
long long directions[8][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1},
                              {1, 0},   {0, 1},  {-1, 0}, {0, -1}};
char a[1005][1005];
bool in_range(long long x) { return (x >= 0 && x < n); }
int main() {
  lg2 = log(2);
  lg3 = log(3);
  cin >> n;
  for (i = 0; i < n; i++) scanf("%s", a[i]);
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (a[i][j] == '3')
        logs[i][j] = lg3;
      else if (a[i][j] == '2')
        logs[i][j] = lg2;
  for (dir = 0; dir < 8; dir++) {
    for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
        if (!in_range(i - directions[dir][0]) ||
            !in_range(j - directions[dir][1])) {
          k = 0;
          long long d1 = directions[dir][0], d2 = directions[dir][1];
          for (x = i, y = j; in_range(x) && in_range(y); x += d1, y += d2) {
            if (a[x][y] != '0') {
              k++;
              if (x == i && y == j)
                sums[dir][x][y] = logs[i][j];
              else
                sums[dir][x][y] = sums[dir][x - d1][y - d2] + logs[x][y];
            } else {
              sums[dir][x][y] = 0;
              k = 0;
            }
            pre[dir][x][y] = k;
          }
        }
  }
  ans = -1;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (a[i][j] != '0') {
        long long tmp = n + 5;
        for (k = 0; k < 4; k++) tmp = min(tmp, pre[k][i][j]);
        double val = logs[i][j];
        for (k = 0; k < 4; k++)
          val += sums[k][i + directions[k][0] * (tmp - 1)]
                     [j + directions[k][1] * (tmp - 1)] -
                 sums[k][i][j];
        if (val > ans) {
          ans = val;
          ansx = i;
          ansy = j;
          anssize = tmp;
          ansdir = 0;
        }
        tmp = n + 5;
        for (k = 4; k < 8; k++) tmp = min(tmp, pre[k][i][j]);
        val = logs[i][j];
        for (k = 4; k < 8; k++)
          val += sums[k][i + directions[k][0] * (tmp - 1)]
                     [j + directions[k][1] * (tmp - 1)] -
                 sums[k][i][j];
        if (val > ans) {
          ans = val;
          ansx = i;
          ansy = j;
          anssize = tmp;
          ansdir = 4;
        }
      }
  total = a[ansx][ansy] - '0';
  for (k = ansdir; k < ansdir + 4; k++) {
    for (i = 1; i < anssize; i++)
      total = (total *
               (a[ansx + directions[k][0] * i][ansy + directions[k][1] * i] -
                '0')) %
              1000000007;
  }
  cout << total << endl;
  return 0;
}
