### Indian National Olympiad in Informatics

### Online Programming Contest, 15-16 April 2006

### Advanced Division

Problem 1: Number of Tilings, *(K Narayan Kumar, CMI)*

You have to tile a room that is two units wide and *N*
units long. You have with you two types of tiles: a rectangle that is
one unit wide and two units long, and an L-shaped tile covering three
square units. Here are pictures of the two types of tiles.

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.

For instance, a 2×3 room can be tiled in 5 different ways,
as follows:

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.

Input format

A single integer *N*, indicating the size of the room.

Output format

The last four digits of the number of ways of tiling the
2×*N* room. If the answer involves fewer than 4 digits,
print the entire answer.

Test Data:

You may assume *N* ≤ 1000000.

Example:

Here is the sample input and output corresponding to the example
discussed above.

Sample Input

13

Sample Output

3465