/*#include <stdio.h>
// 1. 1, 2, 3. ... n출력 하는 재귀함수 만들기
//2. 별을 a개 출력하는 재귀함수 만들기
void f(int a)
{
if(a==0) return;
f(a-1);
printf("*");
}
void f1(int a)
{
if(a==0) return;
f1(a-1);
f(a);
//printf("%d",a);
printf("\n");
}
int main()
{
int a;
scanf("%d",&a);
f1(a);
}*/
/*#include <stdio.h>
void f(int a)
{
if(a==0) return;
f(a-1);
printf("%d ",a);
}
void f2(int a)
{
if(a==0) return;
f2(a-1);
f(a);
printf("\n");
}
int main()
{
int a;
scanf("%d",&a);
f2(a);
}*/
/*#include <stdio.h>
void f5(int a)
{
if(a==0) return;
f5(a-1);
printf("*");
}
void f(int a)
{
if(a==0) return;
f5(a);
printf("\n");
f(a-1);
}
int main()
{
int a;
scanf("%d",&a);
f(a);
}*/
/*#include <stdio.h>
int memo[201]={};
int f(int a)
{
if(memo[a]!=0) return memo[a];
if(a==1 || a==2)
{
return 1;
}
else
{
return memo[a]=(f(a-1)+f(a-2))%10009;
}
}
int main()
{
int a;
scanf("%d",&a);
printf("%d",f(a));
return 0;
}*/