Computer Transformation(hdoj 1041)

Problem Description

A sequence consisting of one digit, the number 1 is initially written into a computer. At each successive time step, the computer simultaneously tranforms each digit 0 into the sequence 1 0 and each digit 1 into the sequence 0 1. So, after the first time step, the sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after the third, the sequence 0 1 1 0 1 0 0 1 and so on.

How many pairs of consequitive zeroes will appear in the sequence after n steps?

Input

Every input line contains one natural number n (0 < n ≤1000).

Output

For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.

Sample Input

2

3

Sample Output

1

1

step 1：01
step 2：1001
step 3：0110 1001
step 4：1001 0110 0110 1001
step 5：0110 1001 1001 0110 1001 0110 0110 1001

 /*找规律，0 1 1 3 5 11 21 43 85，找出递推关系f(n)=2*f(n-2)+f(n-1),*/
 #include<stdio.h>
 int a[][]={{},{},{},{}};
 int b[]={};
 int calc()/*由于n可以取到1000，2^1000超出long long，必须要用数组按位存储，所以考大数*/
 {
     int i=;
     for(i=;i<;i++)
     {
         int c,j;
         for(c=,j=;j<;j++)/*利用b数组存储2*f(n-2)*/
         {
             b[j]=b[j]*+c;/*c为余数*/
             c=b[j]/;
             b[j]=b[j]%;
         }
         for(c=,j=;j<;j++)/* 2*f(n-2)+f(n-1) */
         {
             a[i][j]=b[j]+a[i-][j]+c;
             c=a[i][j]/;
             a[i][j]=a[i][j]%;
         }
     }
 }
 int main()
 {
     int n,i,k=;
     calc();
     while(~scanf("%d",&n))
     {
         if(n==)
             printf("");
         else
         {
             k=;
             for(i=;i>=;i--)
             {
                 if(a[n][i]||k)
                 {
                     printf("%d",a[n][i]);
                     k=;
                 }
             }
         }
         printf("\n");
     }
 }