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;
int n;
int modExp(int b, int e) {
  long long cb = b;
  int ce = e;
  int res = 1;
  while (ce > 0) {
    if (ce % 2 == 1) {
      res = (res * cb) % 1000000007;
    }
    ce /= 2;
    cb = (cb * cb) % 1000000007;
  }
  return res;
}
struct GridNum {
  int exp3, exp2;
  GridNum(int exptwo, int expthree) {
    exp2 = exptwo;
    exp3 = expthree;
  }
  bool is0() { return (exp2 < 0 && exp3 < 0); }
  GridNum operator*(GridNum other) {
    if (is0() || other.is0()) {
      return GridNum(-1, -1);
    } else {
      return GridNum(exp2 + other.exp2, exp3 + other.exp3);
    }
  }
  GridNum operator/(GridNum other) {
    if (other.is0() || is0()) {
      return GridNum(-1, -1);
    } else {
      return GridNum(exp2 - other.exp2, exp3 - other.exp3);
    }
  }
  int collapse() {
    if (is0()) {
      return 0;
    } else {
      return (int)((modExp(2, exp2) * (long long)modExp(3, exp3)) % 1000000007);
    }
  }
  double lnCollapse() {
    if (is0()) {
      return -1;
    } else {
      return exp2 * log(2) + exp3 * log(3);
    }
  }
  bool operator<(GridNum other) { return lnCollapse() < other.lnCollapse(); }
  bool operator>(GridNum other) { return lnCollapse() > other.lnCollapse(); }
};
vector<vector<int>> maxDStraight(vector<vector<GridNum>> &grid) {
  vector<vector<int>> up = vector<vector<int>>(n, vector<int>(n, -1));
  vector<vector<int>> left(up);
  vector<vector<int>> right(up);
  vector<vector<int>> down(up);
  vector<vector<int>> finish(up);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      up[i][j] =
          (i == 0 || grid[i][j].is0() ? -grid[i][j].is0() : up[i - 1][j] + 1);
      left[i][j] =
          (j == 0 || grid[i][j].is0() ? -grid[i][j].is0() : left[i][j - 1] + 1);
      finish[i][j] = min(up[i][j], left[i][j]);
    }
  }
  for (int i = n - 1; i >= 0; --i) {
    for (int j = n - 1; j >= 0; --j) {
      down[i][j] = (i == n - 1 || grid[i][j].is0() ? -grid[i][j].is0()
                                                   : down[i + 1][j] + 1);
      right[i][j] = (j == n - 1 || grid[i][j].is0() ? -grid[i][j].is0()
                                                    : right[i][j + 1] + 1);
      finish[i][j] = min(min(finish[i][j], down[i][j]), right[i][j]);
    }
  }
  return finish;
}
vector<vector<int>> maxDRotated(vector<vector<GridNum>> &grid) {
  vector<vector<int>> upleft = vector<vector<int>>(n, vector<int>(n, -1));
  vector<vector<int>> upright(upleft);
  vector<vector<int>> downleft(upleft);
  vector<vector<int>> downright(upleft);
  vector<vector<int>> finish(upleft);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == 0) {
        upleft[i][j] = -grid[i][j].is0();
        upright[i][j] = upleft[i][j];
      } else {
        upleft[i][j] = (j == 0 || grid[i][j].is0() ? -grid[i][j].is0()
                                                   : upleft[i - 1][j - 1] + 1);
        upright[i][j] =
            (j == n - 1 || grid[i][j].is0() ? -grid[i][j].is0()
                                            : upright[i - 1][j + 1] + 1);
      }
      finish[i][j] = min(upleft[i][j], upright[i][j]);
    }
  }
  for (int i = n - 1; i >= 0; --i) {
    for (int j = n - 1; j >= 0; --j) {
      if (i == n - 1) {
        downleft[i][j] = -grid[i][j].is0();
        downright[i][j] = downleft[i][j];
      } else {
        downleft[i][j] =
            (j == 0 || grid[i][j].is0() ? -grid[i][j].is0()
                                        : downleft[i + 1][j - 1] + 1);
        downright[i][j] =
            (j == n - 1 || grid[i][j].is0() ? -grid[i][j].is0()
                                            : downright[i + 1][j + 1] + 1);
      }
      finish[i][j] = min(finish[i][j], min(downleft[i][j], downright[i][j]));
    }
  }
  return finish;
}
void debugVVGN(vector<vector<GridNum>> toD) {
  cout << "values of vvgn\n";
  for (int i = 0; i < toD.size(); ++i) {
    for (int j = 0; j < toD[i].size(); ++j) {
      cout << toD[i][j].collapse() << ' ';
    }
    cout << endl;
  }
}
int main() {
  string temp;
  cin >> n;
  vector<vector<GridNum>> grid(n, vector<GridNum>(n, GridNum(0, 0)));
  for (int line = 0; line < n; ++line) {
    cin >> temp;
    for (int pos = 0; pos < n; ++pos) {
      if (temp[pos] == '0') {
        grid[line][pos] = GridNum(-1, -1);
      } else {
        grid[line][pos] = GridNum(temp[pos] == '2', temp[pos] == '3');
      }
    }
  }
  vector<vector<int>> maxCrossD = maxDStraight(grid);
  vector<vector<int>> maxRotatedD = maxDRotated(grid);
  vector<vector<GridNum>> rowPartials(n + 1,
                                      vector<GridNum>(n + 1, GridNum(0, 0)));
  vector<vector<GridNum>> colPartials(n + 1,
                                      vector<GridNum>(n + 1, GridNum(0, 0)));
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (i == 0 || j == 0) {
        continue;
      } else if (grid[i - 1][j - 1].is0()) {
        rowPartials[i][j] = GridNum(0, 0);
        colPartials[i][j] = GridNum(0, 0);
      } else {
        rowPartials[i][j] = rowPartials[i][j - 1] * grid[i - 1][j - 1];
        colPartials[i][j] = colPartials[i - 1][j] * grid[i - 1][j - 1];
      }
    }
  }
  vector<vector<GridNum>> drDiagPartials(n + 1,
                                         vector<GridNum>(n + 1, GridNum(0, 0)));
  vector<vector<GridNum>> dlDiagPartials(n + 1,
                                         vector<GridNum>(n + 1, GridNum(0, 0)));
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (i == 0) {
        continue;
      }
      drDiagPartials[i][j] =
          (j == 0 || grid[i - 1][j - 1].is0()
               ? GridNum(0, 0)
               : drDiagPartials[i - 1][j - 1] * grid[i - 1][j - 1]);
      dlDiagPartials[i][j] =
          (j == n || grid[i - 1][j].is0()
               ? GridNum(0, 0)
               : dlDiagPartials[i - 1][j + 1] * grid[i - 1][j]);
    }
  }
  GridNum cMax = GridNum(-1, -1);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (grid[i][j].is0()) {
        continue;
      }
      int sMC = maxCrossD[i][j];
      GridNum rowProduct =
          rowPartials[i + 1][j + sMC + 1] / rowPartials[i + 1][j - sMC];
      GridNum colProduct =
          colPartials[i + sMC + 1][j + 1] / colPartials[i - sMC][j + 1];
      GridNum finalResult = rowProduct * colProduct / grid[i][j];
      cMax = (finalResult > cMax ? finalResult : cMax);
      int sMRC = maxRotatedD[i][j];
      GridNum DRProduct = drDiagPartials[i + 1 + sMRC][j + 1 + sMRC] /
                          drDiagPartials[i - sMRC][j - sMRC];
      GridNum DLProduct = dlDiagPartials[i + 1 + sMRC][j - sMRC] /
                          dlDiagPartials[i - sMRC][j + sMRC + 1];
      finalResult = DRProduct * DLProduct / grid[i][j];
      cMax = (finalResult > cMax ? finalResult : cMax);
    }
  }
  cout << cMax.collapse();
  return 0;
}
