/*#include <stdio.h>
int f(int n)
{
if(n==1) {
return 1;
}
return n + f(n-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
#include <stdio.h>
int f(int n)
{
if(n==1){
return 1;
}
return n * f(n-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
#include <stdio.h>
int f(int n)
{
if(n==1 || n==2){
return 1;
}
if(n==3 || n==4){
return n-1;
}
if(n==5){
return 5;
}
if(n==6){
return 8;
}
if(n==7){
return 13;
}
if(n==8){
return 21;
}
if(n==9){
return 33;
}
if(n==10){
return 54;
}
if(n==11){
return 87;
}
if(n==12){
return 141;
}
if(n==13){
return 228;
}
if(n==14){
return 369;
}
if(n==15){
return 610;
}
if(n==16){
return 979;
}
if(n==17){
return 1589;
}
if(n==18){
return 2568;
}
if(n==19){
return 4157;
}
if(n==20){
return 6765;
}
return f(n-2) + f(n-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
#include <stdio.h>
int f(int n)
{
if(n<=2) {
return 1;
}
return f(n-1) + f(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
#include <stdio.h>
int f(int n)
{
if(n<=2){
return 1;
}
return f(n-1)+f(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n)%10009);
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==1){
return 1;
}
else if(n%2==1){
printf("%d\n",3*n+1);1
f(3*n+1);
}
else{
printf("%d\n",n/2);
f(n/2);
}
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",n);
f(n);
}
#include<stdio.h>
int memo[10000005] = {0};
int pibo(int k) {
if(k<=2) {
return memo[k] = 1;
}
if(memo[k]!=0) {
return memo[k];
}
return memo[k] = pibo(k-1)%10009 + pibo(k-2)%10009;
}
int main() {
int n;
scanf("%d", &n);
printf("%d", pibo(n)%10009);
}
*/
#include <stdio.h>
int memo[10000001];
int f(int a,int k)
{
if(memo[k]!=0){
return memo[k];
}
return memo [k] = f(a-1) + f(a-2) + f(a-3);
}
int main()
{
int a;
scanf("%d",&a);
printf("%d",f(a));
}