CF677E.Vanya and Balloons

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.

万尼亚在一块 $n \times n$ 的方格场上玩气球游戏，每个格子中有一个气球，其值为 $0$、$1$、$2$ 或 $3$ 中的一个。目标是摧毁一个“十字形”（cross），使得该十字形内所有气球的值的乘积尽可能大。十字形分为两类：标准十字形（normal）和旋转十字形（rotated）。例如：

**o**
**o**
ooooo
**o**
**o**

或

o***o
*o*o*
**o**
*o*o*
o***o

形式化地，一个十字形由三个整数 $r$、$c$ 和 $d$ 确定，满足 $d \le r,\,c \le n - d + 1$。

• 标准十字形包含所有坐标为 $(x, y)$（其中 $x$ 表示行号，$y$ 表示列号）的气球，满足

  $$|x - r| \cdot |y - c| = 0 \quad \text{且} \quad |x - r| + |y - c| < d.$$

• 旋转十字形包含所有坐标为 $(x, y)$ 的气球，满足

  $$|x - r| = |y - c| \quad \text{且} \quad |x - r| < d.$$

万尼亚想知道所有可能的十字形中，所含气球数值乘积的最大值。由于该值可能很大，请输出其对 $10^9 + 7$ 取模的结果。

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.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000$）—— 表示气球表格的行数与列数。

接下来的 $n$ 行中，每行包含 $n$ 个字符，每个字符为 '0'、'1'、'2' 或 '3' —— 表示气球中的数值。

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.

输出最大可能乘积对 $10^9 + 7$ 取模的结果。注意，你并非要求最大化对 $10^9 + 7$ 取模后的余数，而是要找出最大值，并将该最大值对 $10^9 + 7$ 取模后输出。

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.

在第一个样例中，当以单元格 $(3, 3)$ 为圆心、半径为 $1$ 构造一个旋转的十字形时，乘积达到最大值：$2·2·3·3·3 = 108$。