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