﻿ Fuzhou University OnlineJudge ﻿
Problem 1640 place blocks

## 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 .

2

3

## Source

FZU 2008 Summer Training II--Combinatorics

Submit  Back  Status  Discuss
﻿