Description
We have a lot of tiles with 2x1 domino shapes, these shapes may be rotated. Given N, please write a function to calculate how many ways are there to tile a 3xN board.
For example, given a 3x2 board, there are 3 ways to tile the board:
Input
The input contains an even integer N (2<=N<=20).
Output
Please output the possible tile counts, it is guaranteed that the answer can be stored in an int, we encourage you to simulate all the possible solution by recursive function, not directly by mathematic recursion.