/*
#include <stdio.h>
int n, k, d[1010];
int upper_bound(int k)
{
int i;
for(i=1; i<=n; i++)
{
if(d[i]>k)
{
return i;
}
}
return n+1;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &d[i]);
scanf("%d", &k);
printf("%d\n", upper_bound(k));
}
/*
#include<stdio.h>
int r(int n)
{
if(n==1)
{
return 1;
}
return n+r(n-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",r(n));
}
/*
#include<stdio.h>
void r(int n)
{
if(n==0)
{
return ;
}
r(n/2);
printf("%d",n%2);
}
int main()
{
int n;
scanf("%d",&n);
if(n==0)
{
printf("0");
}
else
{
r(n);
}
}
/*
#include<stdio.h>
void r(int n)
{
printf("%d\n",n);
if (n==1)
{
return ;
}
if(n%2==1)
{
r(3*n+1);
}
else
{
r(n/2);
}
}
int main()
{
int n;
scanf("%d",&n);
r(n);
}
/*
#include<stdio.h>
void r(int n)
{
if(n==1)
{
return ;
}
if(n%2==1)
{
r(3*n+1);
}
else
{
r(n/2);
}
printf("%d\n",n);
}
int main()
{
int n;
scanf("%d",&n);
printf("1\n");
r(n);
}
/*
#include<stdio.h>
void star(int n) //*을 n개 출력하는 함수
{
if(n==0)
{
return ;
}
star(n-1);
printf("*");
}
void r(int n)
{
if(n==0)
{
return ;
}
r(n-1);
star(n);
printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
r(n);
}*/
#include<stdio.h>
int memo[201]={};
int fib(int n)
{
if(memo[n]!=0)
{
return memo[n];
}
if(n==1||n==2)
{
return memo[n]=1;
}
return memo[n] = (fib(n-1)+fib(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",fib(n));
}