Problem Description
oaiei likes playing building block game. Now he haves a simple question:

the chessboard is a rectangular with the height is N and the width is 3 .

you can only use some 1*1size building blocks and 2*2size building blocks.

you can use a number of 1*1size building blocks and a number of 2*2size building blocks. You should note that the blocks should completely cover the chessboard. The chessboard can not be surplus, and the blocks can not cover each other .
Oaiei knows that you are very smart, and he would like to know there are how many different methods of coverage.
Input
There are multiple test cases. For each test case, there is an integer N, denoting the chessboard is 3*N(1<=N<=10^9).
Output
For each test case, you should output the number of different methods of coverage. Because the answer is too large, so you should print the answer modulo 2^64 on a separate line .
Sample Input
2
Sample Output
3
Source
FZU 2008 Summer Training IICombinatorics