/*
#include <stdio.h>
int f(int n)
{
if(n==1) return 1;
return f(n-1)+n;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
#include<stdio.h>
int f(int n)
{
if(n==1) return 1;
else if(n==2) return 2;
else if(n==3) return 4;
else return f(n-1)+f(n-2)+f(n-3);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
1916 3704 3702
memoization 메모이제이션
어떤 계산 결과를 저장해놓고, 다신 계산하지 않고 가져와서 쓸 수 있도록 하는 기법 (시간이 빨라지는)
if(n==1) return 1;
else if(n==2) return 2;
else if(n==3) return 4;
else return f(n-1)+f(n-2)+f(n-3);
if(n==1) memo[n]=1;
else if(n==2) memo[n]=2;
else if(n==3) memo[n]= 4;
else memo[n] = f(n-1)+f(n-2)+f(n-3);
return memo[n];
*/
/*
#include<stdio.h>
int memo[100001]={};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1) memo[n]=1;
else if(n==2) memo[n]=2;
else if(n==3) memo[n]= 4;
else memo[n] = (f(n-1)+f(n-2)+f(n-3))%1000;
return memo[n];
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
/*
fib 메모이제이션
#include<stdio.h>
int memo[201]={};
int f(int m)
{
if(memo[m]!=0) return memo[m];
if(m==1 || m==2) return memo[m]=1;
return memo[m]=(f(m-1)+f(m-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/
/*
#include<stdio.h>
int memo[51][51]={};
int f(int n,int m)
{
if(memo[n][m]!=0) return memo[n][m];
if(n==1 || m==1) return memo[n][m]=1;
else return memo[n][m]=(f(n-1,m)+f(n,m-1))%100000000;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
printf("%d",f(n,m));
}
*/
#include<stdio.h>
int memo[1000000000]={};
void f(int n)
{
}
int main()
{
}