/*
#include<stdio.h>
void f(int n)
{
if(n==0){
return ;
}
f(n-1);
printf("%d\n",n);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}
*/
/*
#include<stdio.h>
int f(int n)
{
if(n==1){
return;
}
return n+f(n-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
#include <stdio.h>
void star(int n)
{
if(n==0){
return ;
}
printf("*");
return star(n-1);
}
void f(int n)
{
if(n==0){
return ;
}
f(n-1);
//printf("%d",n); //*을 n개 출력하는함수 호출
star(n);
printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}
#include <stdio.h>
int memo[51][51]= {};
int f(int r, int c)
{
if(memo[r][c]!=0)
{
return memo[r][c];
}
if(r==1 || c==1)
{
return memo[r][c]=1;
}
return memo[r][c]=(f(r,c-1)+f(r-1,c))%100000000;
}
int main()
{
int r, c;
scanf("%d %d",&r,&c);
printf("%d",f(r,c));
}
//fibonacci (recursive o memoization o)
#include <stdio.h>
int memo[201]={0};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if(n<=2){
return memo[n]=1;
}
return memo[n]=(f(n-2)+f(n-1))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
#include <stdio.h>
int memo[100001]={};
int f(int n)
{
if(memo[n]!=0){
return memo[n];
}
if(n<=2){
return memo[n]=n;
}
if(n==3){
return memo[n]=4;
}
return memo[n]=(f(n-1)+f(n-2)+f(n-3))%1000;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/