Олимпиадный тренинг

Задача 33143. Ход конем - 2


Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:
 
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
 
Входные данные:  во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).  
 
Выходные данные: выведите единственное число количество способов добраться конём до правого нижнего угла доски.
 
Примеры
Входные данные Выходные данные
1 4 4 2
2 7 15 13309