Игрок находится в помещении прямоугольного плана, где стены расположены как границы прямоугольной таблицы
NxM. При этом в каждой комнате есть 5 проходов влево, вправо, вниз вверх, и вправо вниз(по диагонали).
Игрок хочет выйти как можно быстрее и по этому решил, что даже не будет пытаться ходить вверх и влево.
В начале игрок находится в левой верхней "клетке". И там же он проситал надпись
"Все проходы здесь односторонние. При этом для них верно следующее:
1) Если игрок стоит в клетке, где есть хотя бы одна нечетная координата, то ему разрешалось в неё попасть только из соседних по стороне клетки.
2) Если же обе координаты четные, то войти можно было только по диагонали."
Игроку стало интересно сколько маршрутов ведут к спасительной правой нижней клетке, где точно есть выход.
Требуется найти количество маршрутов, по которым игрок может попасть в правый нижний угол.
Входные данные
В первой строке записаны два числа
N и
M - размеры таблицы .
Выходные данные
Выведите ответ на вопрос задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
|
5
|
|
2
|
4 8
|
10
|