//#include <stdio.h>
//void f(int n)
//{
// if(n==0)
// {
// return ;
// }
// f((n)/2);
// printf("%d",n%2);
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// if(n==0)
// {
// printf("0");
// }
// else
// {
// f(n);
// }
// return 0;
//}
//#include <stdio.h>
//void f(int n)
//{
//
// printf("%d\n",n);
// if(n%2==1)
// {
// f(n*3+1);
// }
// if(n==2)
// {
// printf("1");
// return ;
// }
// if(n%2==0)
// {
// f(n/2);
// }
//
//}
//int main()
//{
// int n;
// scanf("%d",&n);
// if(n==1)
// {
// printf("1");
// }
// else{
// f(n);
// }
// return 0;
//}
//#include <stdio.h>
//void f(int n,int k)
//{
// if(n==0)
// {
// return ;
// }
// f(n/k,k);
// if(n%k>=10)
// {
// printf("%c",n%k+55);
// }
// else
// {
// printf("%d",n%k);
// }
//}
//int main()
//{
// int n,k;
// scanf("%d %d",&n,&k);
// f(n,k);
// return 0;
//}
//#include <stdio.h>
//int f(int n)
//{
// if(n==1||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>
//long long int f(long long int n)2 Sec
//{
// if(n<10)
// {
// return n;
// }
// return f(n/10)+n%10;
//}
//int main()
//{
// long long int n;
// scanf("%lld",&n);
// printf("%lld",f(n));
//
// return 0;
//}
/*
#include <stdio.h>
int a[201]={};
int f(int n)
{
if(a[n]!=0) // 계산한적있어??
{
return a[n]; //그럼 그거 리턴해!
}
if(n==1||n==2)
{
return a[n]=1;
}
return a[n] = ( f(n-1)+f(n-2) )%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/