/*
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
7*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0) return 0;
f(n-1);
printf("*");
}
void f1(int n)
{
if(n==0) return 0;
f1(n-1);
f(n);
printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
f1(n);
//f(n);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==1)
{
printf("1");
return 0;
}
printf("%d\n",n);
if(n%2!=0)
{
f(n*3+1);
}
else if(n%2==0)
{
f(n/2);
}
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==1)
{
printf("1\n");
return 0;
}
if(n%2!=0)
{
f(n*3+1);
}
else
{
f(n/2);
}
printf("%d\n",n);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
1 1 2 3 5 8
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1 || n==2) return 1;
return f(n-1)+f(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/
/*
#include <stdio.h>
int memo[10000] = {0};
int pibo(int k) {
if(k==1 || 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 x;
scanf("%d", &x);
printf("%d", pibo(x)%10009);
return 0;
}
*/
#include <stdio.h>
int memo[10000]={0};
int f(int n)
{
if(n==1 || n==2)
{
return memo[n] = 1;
}
if(memo[n]!=0)
{
return memo[n];
}
return memo[n] = f(n-1) + f(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n)%10009);
return 0;
}