/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include<stdio.h>
void rec(int n)
{
if(n==0)
return;
rec(n-1);
printf("%d\n", n);
}
int main()
{
int n;
scanf("%d", &n);
rec(n);
}
*/
/*
#include<stdio.h>
int memo[10001]={};
int rec(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1||n==2) return memo[n]=n;
return memo[n]=rec(n-1) + rec(n-2);
}
int main()
{
int n;
scanf ("%d",&n);
printf ("%d",rec(n));
return 0;
}
*/
/*
#include<stdio.h>
int memo[10001]={};
int rec(int n, int k)
{
if(memo[n]!=0) return memo[n];
if(n<3) return memo[n]=n;
if(k>0)
return memo[n]=
else
return memo[n]=rec(n-1,0) + rec(n-2,0) + rec(n-3,2);
}
int main()
{
int n,k;
scanf ("%d",&n);
printf ("%d",rec(n,k));
return 0;
}
*/