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 base = 1e9 + 7;
struct node {
  int x, y;
  node operator+(node t) { return (node){x + t.x, y + t.y}; }
  node operator-(node t) { return (node){x - t.x, y - t.y}; }
  node operator*(int t) { return (node){x * t, y * t}; }
  bool operator>=(node t) {
    if (x >= t.x && y >= t.y) return true;
    if (x <= t.x && y <= t.y) return false;
    if (x > t.x) {
      int a = x - t.x, b = t.y - y;
      return log(2) * a > log(3) * b;
    } else {
      int a = y - t.y, b = t.x - x;
      return log(3) * a > log(2) * b;
    }
  }
  void print() { printf("%d %d\n", x, y); }
} sr[1010][1010], sc[1010][1010], sm[1010][1010], sa[1010][1010], a[1010][1010];
int l[1010][1010], r[1010][1010], u[1010][1010], d[1010][1010], lu[1010][1010],
    ld[1010][1010], ru[1010][1010], rd[1010][1010];
char s[1010][1010];
int n, m;
bool check() {
  for (int i = (1), _b = (n); i <= _b; i++)
    for (int j = (1), _b = (n); j <= _b; j++)
      if (s[i][j] != '0') return true;
  return false;
}
void input() {
  scanf("%d", &n);
  for (int i = (1), _b = (n); i <= _b; i++) scanf("%s", s[i] + 1);
}
void init() {
  for (int i = (1), _b = (n); i <= _b; i++) {
    for (int j = (1), _b = (n); j <= _b; j++) {
      a[i][j].x = (s[i][j] == '2');
      a[i][j].y = (s[i][j] == '3');
      if (s[i][j] == '0') continue;
      l[i][j] = l[i][j - 1] + 1;
      u[i][j] = u[i - 1][j] + 1;
      lu[i][j] = lu[i - 1][j - 1] + 1;
      ru[i][j] = ru[i - 1][j + 1] + 1;
      sr[i][j] = sr[i][j - 1] + a[i][j];
      sc[i][j] = sc[i - 1][j] + a[i][j];
      sm[i][j] = sm[i - 1][j - 1] + a[i][j];
      sa[i][j] = sa[i - 1][j + 1] + a[i][j];
    }
    for (int j = (n), _b = (1); j >= _b; j--)
      if (s[i][j] != '0') r[i][j] = r[i][j + 1] + 1;
  }
  for (int i = (n), _b = (1); i >= _b; i--)
    for (int j = (1), _b = (n); j <= _b; j++)
      if (s[i][j] != '0') {
        d[i][j] = d[i + 1][j] + 1;
        ld[i][j] = ld[i + 1][j - 1] + 1;
        rd[i][j] = rd[i + 1][j + 1] + 1;
      }
}
void solve() {}
long long pw(int x, int k) {
  long long res = 1;
  long long a = x;
  int b = k;
  for (; b; b >>= 1, a = a * a % base)
    if (b & 1) res = res * a % base;
  return res;
}
void output() {
  node res = (node){0, 0};
  for (int i = (1), _b = (n); i <= _b; i++)
    for (int j = (1), _b = (n); j <= _b; j++)
      if (s[i][j] != '0') {
        int t;
        node tmp;
        t = min(min(l[i][j], r[i][j]), min(u[i][j], d[i][j]));
        tmp = sr[i][j + t - 1] - sr[i][j - t] + sc[i + t - 1][j] -
              sc[i - t][j] - a[i][j];
        if (tmp >= res) res = tmp;
        t = min(min(lu[i][j], ld[i][j]), min(ru[i][j], rd[i][j]));
        tmp = sm[i + t - 1][j + t - 1] - sm[i - t][j - t] +
              sa[i + t - 1][j - t + 1] - sa[i - t][j + t] - a[i][j];
        if (tmp >= res) res = tmp;
      }
  printf("%I64d", pw(2, res.x) * pw(3, res.y) % base);
}
int main() {
  input();
  if (!check()) {
    printf("0");
    return 0;
  }
  init();
  solve();
  output();
  return 0;
}
