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 23 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 24 room.

Given N, your task is to determine the number of ways to tile a room of size 2N. 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 213 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.


The input contains multiple test cases. For each test case, a single integer N(N<=1000000), indicating the size of the room.


For each test case, output the last four digits of the number of ways of tiling the 2N room. If the answer involves fewer than 4 digits, print the entire answer.

Sample Input


Sample Output