Ваня играет в игру, в которой на поле размером 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.

Ваня хочет узнать максимально возможное произведение значений шариков, образующих один крест. Поскольку ответ может быть слишком большим, Ваня хочет знать это число по модулю 10⁹ + 7.