I

Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

 1 #include<cstdio>
 2 using namespace std;
 3 int f(int n)
 4 {
 5     if(n==0)
 6         return 1;
 7     if(n==2)
 8         return 3;
 9     else
10         return 4*f(n-2)-f(n-4);
11 }
12 int main()
13 {
14     int n;
15     while(scanf("%d",&n)==1&&n!=-1)
16         if(n%2==0)
17         printf("%d
",f(n));
18         else
19         printf("%d
",0);
20     return 0;
21 }

Description

In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

Input

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30.

Output

For each test case, output one integer number giving the number of possible tilings.

Sample Input

Sample Output