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