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: or 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 . 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. 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. 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 .