Given a rectangular board
N × M (
N rows and
M columns). In the upper left corner is a chess knight, which must be moved to the lower right corner of the board. In this case, the horse can only walk as shown in the figure:
We need to determine how many different routes there are from the top left to the bottom right corner.
Input: the input string contains two natural numbers N and M (< span class="math-tex">\(1 <= N,\ M <= 15\)).
Output: print a single number of ways to get the knight to the bottom right corner of the board.
Examples
| # |
Input |
Output |
| 1 |
4 4 |
2 |
| 2 |
7 15 |
13309 |