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。