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