/*
f(n) : n번째 피보나치수
: n-1번째 피보나치수 + n-2번째피보나치수
f(1) : return 1;
f(2) : return 1;
f(3) :
*/
/*
#include <stdio.h>
int f(int n)
{
if(n<=2)
{
return 1;
}
return f(n-1)+f(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/
/*
#include <stdio.h>
void f(int k)
{
if (k==1)
{
printf("%d\n",1);
return ;
}
if (k % 2 == 1)
f(3*k+1);
else
f(k/2);
printf("%d\n", k);
}
int main()
{
int n;
scanf("%d", &n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
void star(int n)
{
if(n==0)
return;
printf("*");
star(n-1);
}
void f(int n)
{
if(n==0)
return ;
f(n-1);
star(n);
printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
star(n);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0)
{
printf("0");
return ;
}
if(n==1)
{
printf("1");
return ;
}
f(n/2);
printf("%d",n%2);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
int m[201]={};
//m[n]에 f(n)값을 저장해놓고 다시 재귀함수를 돌리지 않도록
int f(int n)
{
if(m[n]!=0) return m[n];
if(n<=2)
{
return m[n]=1;
}
return m[n]=(f(n-1)+f(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/