We have a lot of tiles with 2x1 domino shapes, these shapes may be rotated. Given N and M, please write a function to calculate how many ways are there to tile a NxM board.
For example, given a 3x2 board, there are 3 ways to tile the board:
The input contains two integers N, M (2 <= NxM <= 50). It is guaranteed that at least one of them is even.
Please output the possible tile counts, followed by a newline.