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;
template <typename T>
T nextInt() {
  T x = 0, p = 1;
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') {
    p = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * p;
}
const int maxN = (int)1e3 + 10;
const int maxL = 17;
const int INF = (int)1e9;
const int mod = (int)1e9 + 7;
const long long LLINF = (long long)1e18 + 5;
struct state {
  int dx, dy;
  int len[maxN][maxN];
  int cnt2[maxN][maxN];
  int cnt3[maxN][maxN];
  state() {
    memset(len, 0, sizeof len);
    memset(cnt2, 0, sizeof cnt2);
    memset(cnt3, 0, sizeof cnt3);
  }
  state(int dx, int dy) : dx(dx), dy(dy) {}
  void upd(int i, int j, int val) {
    if (val == 0) {
      len[i][j] = 0;
    } else {
      len[i][j] = len[i + dx][j + dy] + 1;
    }
    cnt2[i][j] = cnt2[i + dx][j + dy] + (val == 2);
    cnt3[i][j] = cnt3[i + dx][j + dy] + (val == 3);
  }
  void add(int i, int j, int d, pair<int, int> &answer) {
    answer.first += cnt2[i][j] - cnt2[i + dx * (d + 1)][j + dy * (d + 1)];
    answer.second += cnt3[i][j] - cnt3[i + dx * (d + 1)][j + dy * (d + 1)];
  }
};
int n;
char s[maxN][maxN];
state *T[3][3];
void update(pair<int, int> &answer, pair<int, int> &cur) {
  long double p = log(2) * answer.first + log(3) * answer.second;
  long double p2 = log(2) * cur.first + log(3) * cur.second;
  if (p2 > p) {
    answer = cur;
  }
}
int main() {
  n = nextInt<int>();
  for (int i = 1; i <= n; ++i) {
    gets(s[i] + 1);
  }
  for (int i = -1; i < 2; ++i) {
    for (int j = -1; j < 2; ++j) {
      T[i + 1][j + 1] = new state(i, j);
    }
  }
  bool haveOne = false;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (s[i][j] == '1') haveOne = true;
      T[-1 + 1][0 + 1]->upd(i, j, s[i][j] - '0');
      T[0 + 1][-1 + 1]->upd(i, j, s[i][j] - '0');
      T[-1 + 1][-1 + 1]->upd(i, j, s[i][j] - '0');
    }
  }
  for (int i = n; i >= 1; --i) {
    for (int j = n; j >= 1; --j) {
      if (s[i][j] == '1') haveOne = true;
      T[+1 + 1][0 + 1]->upd(i, j, s[i][j] - '0');
      T[0 + 1][+1 + 1]->upd(i, j, s[i][j] - '0');
      T[+1 + 1][+1 + 1]->upd(i, j, s[i][j] - '0');
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = n; j >= 1; --j) {
      T[-1 + 1][+1 + 1]->upd(i, j, s[i][j] - '0');
    }
  }
  for (int i = n; i >= 1; --i) {
    for (int j = 1; j <= n; ++j) {
      T[+1 + 1][-1 + 1]->upd(i, j, s[i][j] - '0');
    }
  }
  pair<int, int> answer = make_pair(0, 0);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      int d = INF;
      for (int dx = -1; dx < 2; ++dx) {
        for (int dy = -1; dy < 2; ++dy) {
          if (abs(dx) + abs(dy) != 1) continue;
          d = min(d, T[dx + 1][dy + 1]->len[i][j]);
        }
      }
      d--;
      pair<int, int> cur_answer = make_pair(0, 0);
      if (s[i][j] == '2') cur_answer.first++;
      if (s[i][j] == '3') cur_answer.second++;
      update(answer, cur_answer);
      if (d == -1 || s[i][j] == '0') continue;
      for (int dx = -1; dx < 2; ++dx) {
        for (int dy = -1; dy < 2; ++dy) {
          if (abs(dx) + abs(dy) != 1) continue;
          T[dx + 1][dy + 1]->add(i, j, d, cur_answer);
        }
      }
      if (s[i][j] == '2') {
        cur_answer.first -= 4;
      }
      if (s[i][j] == '3') {
        cur_answer.second -= 4;
      }
      update(answer, cur_answer);
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      int d = INF;
      for (int dx = -1; dx < 2; ++dx) {
        for (int dy = -1; dy < 2; ++dy) {
          if (abs(dx) + abs(dy) != 2) continue;
          d = min(d, T[dx + 1][dy + 1]->len[i][j]);
        }
      }
      d--;
      pair<int, int> cur_answer = make_pair(0, 0);
      if (s[i][j] == '2') cur_answer.first++;
      if (s[i][j] == '3') cur_answer.second++;
      update(answer, cur_answer);
      if (d == -1 || s[i][j] == '0') continue;
      for (int dx = -1; dx < 2; ++dx) {
        for (int dy = -1; dy < 2; ++dy) {
          if (abs(dx) + abs(dy) != 2) continue;
          T[dx + 1][dy + 1]->add(i, j, d, cur_answer);
        }
      }
      if (s[i][j] == '2') {
        cur_answer.first -= 4;
      }
      if (s[i][j] == '3') {
        cur_answer.second -= 4;
      }
      update(answer, cur_answer);
    }
  }
  if (answer == make_pair(0, 0)) {
    printf("%d\n", haveOne);
  } else {
    long long ret = 1;
    while (answer.first--) {
      ret = (ret * 2) % mod;
    }
    while (answer.second--) {
      ret = (ret * 3) % mod;
    }
    printf("%I64d\n", ret);
  }
  return 0;
}
