Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Vanya and Balloons

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputVanya 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 10^{9} + 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 10^{9} + 7. Note, that you are not asked to maximize the remainder modulo 10^{9} + 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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 06:26:47 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|