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>
char grid[1000][1000];
void update(int a[], const int b[]) {
  static const double x = log(2);
  static const double y = log(3);
  if ((a[2] < b[2] || a[3] < b[3]) &&
      ((a[2] < b[2] + 1 && a[3] < b[3] + 1) ||
       (a[2] - b[2]) * x + (a[3] - b[3]) * y < 0)) {
    a[2] = b[2];
    a[3] = b[3];
  }
}
int64_t powmod(int64_t a, int n, const int64_t mod) {
  int64_t out = 1;
  for (; 0 < n; n >>= 1, a = (a * a) % mod)
    if (n & 1) out = (out * a) % mod;
  return out;
}
int e677() {
  int n, i, j, r;
  int out[4] = {0, 0, -1, -1};
  const int64_t mod = 1000000007;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) {
    scanf("%s", grid[i]);
    for (j = 0; j < n; ++j) grid[i][j] -= '0';
  }
  for (i = 0; i < n; ++i) {
    const int s = ((i + 1) < (n - i) ? (i + 1) : (n - i));
    for (j = 0; j < n; ++j)
      if (grid[i][j]) {
        const int u = ((j + 1) < (n - j) ? (j + 1) : (n - j));
        const int t = ((s) < (u) ? (s) : (u));
        int val[4] = {0, 0, 0, 0};
        ++val[grid[i][j]];
        for (r = 1; r < t && grid[i - r][j] && grid[i][j - r] &&
                    grid[i + r][j] && grid[i][j + r];
             ++r) {
          ++val[grid[i - r][j]];
          ++val[grid[i][j - r]];
          ++val[grid[i + r][j]];
          ++val[grid[i][j + r]];
        }
        update(out, val);
      }
  }
  for (i = 0; i < n; ++i) {
    const int s = ((i + 1) < (n - i) ? (i + 1) : (n - i));
    for (j = 0; j < n; ++j)
      if (grid[i][j]) {
        const int u = ((j + 1) < (n - j) ? (j + 1) : (n - j));
        const int t = ((s) < (u) ? (s) : (u));
        int val[4] = {0, 0, 0, 0};
        ++val[grid[i][j]];
        for (r = 1; r < t && grid[i + r][j + r] && grid[i + r][j - r] &&
                    grid[i - r][j + r] && grid[i - r][j - r];
             ++r) {
          ++val[grid[i + r][j + r]];
          ++val[grid[i + r][j - r]];
          ++val[grid[i - r][j + r]];
          ++val[grid[i - r][j - r]];
        }
        update(out, val);
      }
  }
  return out[2] < 0 ? 0 : powmod(2, out[2], mod) * powmod(3, out[3], mod) % mod;
}
int main() {
  printf("%d", e677());
  return EXIT_SUCCESS;
}
