/*
这个代码对我自己来说,写的算是比较工整了(大牛勿BS);
里面的函数可以当模板用
*/
#include <stdio.h>
#include <string.h>
char dpM[1100][1100],dpF[1100][1100];
void in_add(char s[], char max[],char min[])
{
int l1=strlen(max);
int l2=strlen(min);
int yu=0,i;
for(i=0;i<l2;i++)
{
s[i]=((yu + (min[i] - '1' + 1) + (max[i] - '1' + 1)) % 10) + '1' - 1;
yu = ((yu + (min[i] - '1' + 1) + (max[i] - '1' + 1)) / 10);
}
for(i=l2;i<l1;i++)
{
s[i] = ((yu + max[i] - '1' + 1) % 10) + '1' - 1;
yu = (( yu + max[i] - '1' + 1) / 10);
}
if(yu){
s[l1] = yu + '1' - 1;
}
}
void ADD(char s[] , char a[] , char b[])
{
int l1=strlen(a);
int l2=strlen(b);
in_add( s, l1 >= l2 ? a : b, l1 < l2 ? a : b);
}
void Print( char max[], char min[])
{
int l1=strlen(max);
int l2=strlen(min);
int s[1000];
int yu=0,a,b,i;
for(i=0;i<l2;i++)
{
s[i] = (yu + (min[i] - '1' + 1) + (max[i] - '1' + 1)) % 10;
yu = (yu + (min[i] - '1' + 1) + (max[i] - '1' + 1)) / 10;
}
for(i=l2;i<l1;i++)
{
s[i] = ( yu + max[i] - '1' + 1) % 10;
yu = ( yu + max[i] - '1' + 1) / 10;
}
if(yu) printf("%d",yu);
for(i=l1-1;i>=0;i--)
{
printf("%d",s[i]);
}
printf("\n");
}
int main()
{
int n;
int i,l1,l2;
strcpy( dpM[1] , "1");
strcpy( dpF[1] , "0");
strcpy( dpM[2] , "1");
strcpy( dpF[2] , "1");
for( i = 3; i <= 1000; i++)
{
ADD( dpM[i], dpF[i - 1], dpM[i - 1]);
ADD( dpF[i], dpM[i - 2], dpF[i - 1]);
// dpM[i] = dpF[i - 1] + dpM[i - 2];
// dpF[i] = dpM[i - 1] + dpF[i - 1];
}
while(scanf("%d",&n)!=EOF)
{
l1=strlen(dpM[n]);
l2=strlen(dpF[n]);
Print( l1 >= l2 ? dpM[n] : dpF[n] , l1 < l2 ? dpM[n] : dpF[n]);
}
return 0;
}