/*
#include <stdio.h>
long long int n;
long long int sqrt(long long int n)
{
long long int i;
for(i=0; ; i++)
{
if(i*i>n)
{
return i-1;
break;
}
else if(i*i==n)
{
return i;
break;
}
}
}
// 이 부분에 들어가야 될 코드를 작성하여 제출
int main()
{
scanf("%lld", &n);
printf("%d\n", sqrt(n));
return 0;
}
*/
/*
#include <stdio.h>
int myabs(int a)
{
if(a>=0)
{
return a;
}
else
{
return -a;
}
}
// 이 부분에 들어가야 될 코드를 작성하여 제출
main()
{
int a;
scanf("%d", &a);
printf("%d", myabs(a));
}
*/
/*
#include<stdio.h>
int hab(int n)///자릿수의 합 함수
{
int i, s=0, p;
p=n;
for(; p!=0; )
{
s+=(p%10);
p/=10;
}
return s+n;
}
int main()
{
int su[6000]={0};
int i, a, b, s=0;
scanf("%d %d", &a, &b);
for(i=1; i<b; i++)
{
su[hab(i)]=1;
}
for(i=a; i<=b; i++)
{
if(su[i]==0)
{
s+=i;
}
}
printf("%d", s);
}
*/
/*
#include<stdio.h>
void swap(int *x, int *y) {
int t;
t = *x;
*x = *y;
*y = t;
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
printf("%d %d\n", a, b);
swap(&a, &b);
printf("%d %d\n", a, b);
}
*/
/*
#include <stdio.h>
void myswap(int *x, int *y)
{
int t;
if(*x>=*y)
{
t=*x;
*x=*y;
*y=t;
}
}
// 이 부분에 들어가야 될 코드를 작성하여 제출
main()
{
int a, b;
scanf("%d%d", &a, &b);
myswap(&a, &b);
printf("%d %d", a, b);
}
*/
/*
#include <stdio.h>
int n;
int f(int n)
{
int i, s=0;
for(i=1; i<=n; i++)
{
if(n%i==0)
{
s+=1;
}
}
return s;
}
// 이 부분에 들어가야 될 코드를 작성하여 제출
int main()
{
scanf("%d", &n);
printf("%d\n", f(n));
}
*/
/*
#include <stdio.h>
int gcd(int p, int q)
{ if(p==0) return q; return gcd(q%p, p);}
long long int lcm(long long int a, long long int b)
{
long long int t;
t=a*b/gcd(a, b);
return t;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%lld\n", lcm(a, b));
}
*/
/*
#include <stdio.h>
void f()
{
printf("Hello?");
}
// 이 부분에 들어가야 될 코드를 작성하여 제출
main()
{
f();
}
*/
/*
// recurse: 재귀
#include<stdio.h>
void show(int x) {
if (x == 0) return;
show(x-1);
printf("HELLOWORLD %d\n", x);
}
int main() {
show(5);
}
*/
/*
#include<stdio.h>
void show(int n)
{
if(n==0) return;
show(n-1);
printf("%d\n", n);
}
int main()
{
int n;
scanf("%d", &n);
show(n);
}
*/
/*
#include<stdio.h>
void show(int n)
{
if(n==0) return;
printf("%d\n", n);
show(n-1);
}
int main()
{
int n;
scanf("%d", &n);
show(n);
}
*/
/*
#include<stdio.h>
void show(int n)///입력된 수로부터 홀수만 큰 수 부터 출력
{
if(n<=0)
return;
if(n%2==1)
{
printf("%d\n", n);
n=n-2;
show(n);
}
else
{
n=n-1;
printf("%d\n", n);
n=n-2;
show(n);
}
}
int main()
{
int n;
scanf("%d", &n);
show(n);
}
*/
/*
#include<stdio.h>
void show(int a, int b)///입력된 두 수로부터 홀수만 출력
{
if(a>b)
{
return;
}
if(a%2==1) {
printf("%d ", a);
}
show(a+1, b);
///재귀는 1씩 뛰면서 하는데 프린트는 걸러서 출력
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
show(a, b);
}
*/
/*
#include<stdio.h>
int s=0;
void f(int n)
{
if(n==0)
{
printf("%d", s);
return;
}
s+=n;
f(n-1);
}
int main()
{
int n;
scanf("%d", &n);
f(n);
}
*/
/*
#include<stdio.h>
void f(int n)
{
if(n==0)
{
printf("%d", s);
return;
}
s*=n;
f(n-1);
}
int main()
{
int n;
scanf("%d", &n);
f(n);
}
*/
/*
#include<stdio.h>
int rec(int x) {
if(x==1) {
return 1;
}
return x + rec(x-1);
}
int main() {
int n;
scanf("%d", &n);
printf("%d", rec(n));
}
*/
/*
#include<stdio.h>
int rec(int n)
{
if(n==0)
{
return 0;
}
return n+rec(n-1);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", rec(n));
}
*/
/*
#include<stdio.h>
int sec(int n)
{
if(n==1)
{
return 1;
}
return n*sec(n-1);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", sec(n));
}
*/
/*
#include<stdio.h>
int pibo(int n)
{
if(n==1)
{
return 1;
}
else if(n==2)
{
return 1;
}
else if(n>=3)
{
return pibo(n-1)+pibo(n-2);
}
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", pibo(n));
}
*/
/*
#include<stdio.h>
void ham(int n)
{
printf("%d\n", n);
if(n==1)
{
return;
}
if(n%2==0)
{
ham(n/2);
}
else
{
ham(3*n+1);
}
}
int main()
{
int n;
scanf("%d", &n);
ham(n);
}
*/
/*
#include<stdio.h>
void ham(int n)
{
if(n==1)
{
printf("1\n");
return;
}
if(n%2==0)
{
ham(n/2);
}
else
{
ham(3*n+1);
}
printf("%d\n", n);
}
int main()
{
int n;
scanf("%d", &n);
ham(n);
}
*/
#include<stdio.h>
int su[206]= {0};
int pibo( int n)
{
if(n<=2)
{
return su[n]=n;
}
if(su[n]!=0)
{
return su[n];
}
return su[n]=pibo(n-1)%10009+pibo(n-2)%10009;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", pibo(n)%10009);
}