/*
#include <stdio.h>
void star(int n)
{
printf("*");
if(n==1) return;
star(n-1);
}
void rec(int n)
{
if(n==0) return;
rec(n-1);
star(n);
printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
return 0;
}
*/
/*
1부터 n까지의 합 = 1~ n-1까지의합 +n
rec(int n)
{
if(n==1) return 1;
return rec(n-1)+n;
}
s(k,n) = s(k-1,1) + ... +s(k-1,n-1) + s(k-1,n);
=s(k,n-1) + s(k-1,n) ;
*/
/*
#include<stdio.h>
int SuperSum(int k,int n)
{
if(k==0)
return n;
if(n==0)
return 0;
return SuperSum(k,n-1)+SuperSum(k-1,n);
}
int main()
{
int k,n;
while( scanf("%d %d", &k, &n) != EOF )
printf("%d\n", SuperSum(k, n));
}
*/
/*
#include<stdio.h>
void rec(int n)
{
if(n==0)
{
return ;
}
rec(n/2);
printf("%d",n%2);
}
int main()
{
int n;
scanf("%d",&n);
if(n==0)
{
printf("0");
return 0;
}
rec(n);
}
*/
/*
#include<stdio.h>
int main()
{
int i,a,b,c,d,x,max=0,min=10000000;
scanf("%d %d",&a,&b);
for(i=a; i<=b; i++)
{
x=i;
while(x!=1)
{
if(x%2==0)
{
x=x/2;
}
else if(x%2!=0)
{
x=3*x+1;
}
c++;
}
if(max<c)
{
d=i;
max=c;
}
}
printf("%d %d",d,c);
}
memoization
int arr[50]
arr[k] = k번째 들어온 data (x)
arr[k] = k에 관련된 정보 (o)
memo[n] = n 번째 피보나치 수
계산을 했던 수는 다시 계산을 하지 않는다.
계산 횟수를 많이 줄일 수 있다!
*/
/*
#include<stdio.h>
int memo[201]={};
int fib(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1 || n==2) return memo[n]=1;
return memo[n]=(fib(n-1) + fib(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",fib(n));
return 0;
}