You are allowed to rotate the tiles when you lay them. You have an infinite supply of both types of tiles. Your objective is to calculate the number of different ways of tiling the room using these tiles.
Notice that a tiling can use both types of tiles. Consider, for instance, the following tiling of a 2¡Á4 room.
Given N, your task is to determine the number of ways to tile a room of size 2¡ÁN. Since this number may be very large, it is sufficient to report the last four digits of the answer. For instance the number of ways to tile a 2¡Á13 room is 13465. Your program should just print 3465. If the answer involves fewer than 4 digits then print the entire answer. For example, if N = 3 you should print 5.