跳马问题(Knight Jumps)

题目描述

在 n 行 m 列的棋盘上有一只中国象棋中的马。马走“日”字，并且题目规定马只能往右走。请你求出马从棋盘的左下角 (0,0) 走到右上角 (m,n) 一共有多少条不同的可行路径。

坐标约定：x 表示列（范围 0~m），y 表示行（范围 0~n）。从格子 (x, y) 出发，马走“日”字且只能往右（列坐标增大），一步可以到达的四个格子为：

• (x+1, y+2)
• (x+2, y+1)
• (x+2, y-1)
• (x+1, y-2)

马不能走出棋盘边界（即必须满足 0 ≤ x ≤ m 且 0 ≤ y ≤ n）。

输入格式

一行两个整数 n 和 m，表示棋盘有 n 行、m 列。

输出格式

一个整数，表示从 (0,0) 走到 (m,n) 的可行路径条数。

样例输入

4 8

样例输出

37

数据范围

n, m ≤ 20。答案不超过 int 范围。