Indian National Olympiad in Informatics

Related:

Online Programming Contest, 15-16 April 2006

IARCS home > OLYMPIAD

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

Sample Output