斑的家

import java.math.BigInteger;
import java.util.*;
/*
 * AUTHOR : benbendog
 * DATE   : 2010/12/22
 * PROBLEM: given 2x1,2x2 tile, how many ways can we arrange to put tiles
            in a 2xn rectangles
 * SOLUTION: f(i) = f(i-1) + 2(f-2) , f(0) = 1 ,f(1) = 1
 */
class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner cin = new Scanner(System.in);
        BigInteger bg[] = new BigInteger[251];
        bg[0] = BigInteger.ONE;
        bg[1] = BigInteger.ONE;
        int n,i;
        for(i = 2 ; i < 251 ; i++)
        {
            bg[i] = bg[i-1].add(bg[i-2].add(bg[i-2]));
        }
        while(cin.hasNext())
        {
            n= cin.nextInt();
            System.out.println(bg[n]);
        }
    }

}