Ход конем
Дана прямоугольная доска N∗M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.

Входные данные

В первой строке входного файла находятся два натуральных числа N и M (1≤N,M≤15).

Выходные данные

В выходной файл выведите единственное число — количество добраться конём до правого нижнего угла доски.

Примеры
Ввод
4 4
Вывод
2
Ввод
7 15
Вывод На любом из языков(Java)(C++)(Python)

Для решения данной задачи можно использовать динамическое программирование.

Введем двумерный массив dp размером (N+1)×(M+1), в котором dp[i][j] будет хранить количество различных маршрутов, ведущих из левого верхнего угла доски в клетку (i,j).

Инициализируем массив dp следующим образом:
- dp[0][0] = 1 (начальная клетка)
- dp[1][2] = 1 (второй ход коня)
- dp[2][1] = 1 (второй ход коня)

Затем переберем все клетки доски по строкам и столбцам, начиная с (1,1), и заполним массив dp по формуле:
- dp[i][j] = dp[i-1][j-2] + dp[i-2][j-1]

То есть количество путей до клетки (i,j) равно сумме количества путей до клеток, из которых конь может сделать ход в клетку (i,j).

Наконец, ответом на задачу будет являться значение dp[N][M].

Пример решения на языке Python:

```python
N, M = map(int, input().split())

dp = [[0] * (M+1) for _ in range(N+1)]

dp[0][0] = 1
dp[1][2] = 1
dp[2][1] = 1

for i in range(1, N+1):
for j in range(1, M+1):
dp[i][j] = dp[i-1][j-2] + dp[i-2][j-1]

print(dp[N][M])
```

Данное решение имеет сложность O(N*M), что является эффективным для указанных ограничений размера доски.