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.
Output
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.