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