CF677E Vanya and Balloons
Description
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
**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
Input Format
The first line of the input contains a single integer $ n $ ( $ 1
Output Format
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.
Explanation/Hint
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 $ .