Дано поле $$$n \times m$$$, каждая клетка которого заблокирована или свободна.

Монокарп ставит робота в некоторую свободную клетку поля, а затем запускает его по некоторому циклическому маршруту. За один ход робот может переместиться в свободную клетку, соседнюю по стороне или по углу с текущей. Маршрут должен удовлетворять следующим условиям:

• маршрут должен начинаться и заканчиваться в одной и той же клетке;
• маршрут должен заходить в каждую клетку не более одного раза (считаем, что в начале маршрута робот не заходит в стартовую клетку, а уже там находится);
• робот изменяет направление движения ровно три раза.

Например, робот может начать в некоторой клетке, пойти два раза направо, два раза вниз-влево и два раза наверх. Так как маршрут циклический, робот меняет направление трижды: направо $$$\rightarrow$$$ вниз-влево $$$\rightarrow$$$ наверх $$$\rightarrow$$$ направо.

Два маршрута считаются различными, если:

• либо робот посещает в одном маршруте клетку, которую не посещает в другом;
• либо клетки в маршруте расположены в разном порядке.

Обратите внимание, что маршрут циклический, поэтому два маршрута, отличающиеся только стартовой клеткой, на самом деле не считаются различными.

Сколько различных маршрутов для робота может выбрать Монокарп?