提示: 欢迎访问OurACM平台。
Problem 1640 place blocks

Accept: 49    Submit: 119
Time Limit: 1000 mSec    Memory Limit : 32768 KB

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*1-size building blocks and 2*2-size building blocks.
  • you can use a number of 1*1-size building blocks and a number of 2*2-size 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 II--Combinatorics

Submit  Back  Status  Discuss