Анонс #204. Ход коня

Задача: дана прямоугольная доска N×M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке, конь не может выходить за границы доски.

Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.

Входные данные: N и M, где (1 ⩽ N,M ⩽ 15).

Вывод: количество способов добраться конём до правого нижнего угла доски.

Примеры:

1. N = M = 4;

Output: 2;

2. N = 15, M = 14;

Output: 7884330