← 返回题目列表

Codeforces · 677/E

E. 万尼亚和气球

中文机器翻译题面 查看原题

Vanya 在大小为 n × n 的场地上玩气球游戏,其中每个单元格都包含一个值为 0、1、2 或 3 之一的气球。目标是破坏一个十字,使十字中气球的所有值的乘积尽可能最大。有两种类型的十字:正常十字和旋转十字。例如:

or

形式上,十字由三个整数 r、c 和 d 给出,使得 d ≤ r、c ≤ n - d + 1。正常十字由位于单元格 (x, y) 中的气球组成(其中 x 表示行数,y 表示列数),这样 |x - r|·|y - c| = 0 和 |x - r| + |y - c| <d。旋转十字由位于单元格 (x, y) 中的气球组成,使得 |x - r| = |y - c|和 |x - r| <d。

Vanya 想知道形成一个十字的球的值的最大可能乘积。由于该值可能很大,因此输出它对 109 + 7 求模。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 1000) - 带气球的表格中的行数和列数。

以下 n 行中的每一行包含 n 个字符“0”、“1”、“2”或“3”——气球中值的描述。

输出

打印模 109 + 7 的最大可能乘积。请注意,系统不会要求您最大化模 109 + 7 的余数,而是找到最大值并打印该模。

示例

输入 #1

4
1233
0213
2020
0303

输出 #1

108

输入 #2

5
00300
00300
33333
00300
00300

输出 #2

19683

输入 #3

5
00003
02030
00300
03020
30000

输出 #3

108

输入#4

5
21312
10003
10002
10003
23231

输出#4

3

输入 #5

5
12131
12111
12112
21311
21212

输出 #5

24

注意

在第一个示例中,以单元格 (3, 3) 为中心、半径为 1 的旋转十字获得了最大乘积:2·2·3·3·3 = 108。