Ваня играет в игру, в которой на поле размером n × n в каждой клетке находится шарик со значением 0, 1, 2 или 3. Требуется за один ход уничтожить крест из шариков, такой что произведение значений составляющих его шариков максимально. Кресты из шариков могут быть обычные и повёрнутые. Например:
**o**
**o**
ooooo
**o**
**o**
или
o***o
*o*o*
**o**
*o*o*
o***o
Формально, крест задаётся тремя целыми числами 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.
Ваня хочет узнать максимально возможное произведение значений шариков, образующих один крест. Поскольку ответ может быть слишком большим, Ваня хочет знать это число по модулю 109 + 7.
Выходные данные
Выведите самое большое возможное произведение по модулю 109 + 7. Обратите внимание, что требуется не максимизировать остаток от деления, а найти максимальное число и вывести его по модулю 109 + 7.